diff options
| author | Julien M'Poy <julien.mpoy@gmail.com> | 2017-11-08 13:29:24 +0100 |
|---|---|---|
| committer | Julien M'Poy <julien.mpoy@gmail.com> | 2017-11-08 13:29:24 +0100 |
| commit | 5e81853768c0f3cc55c05e0dfec18773045df952 (patch) | |
| tree | b62c3fb0bfc6de3318e962b330e163f3d65cdfa6 /dynamic-programming.html.markdown | |
| parent | 20893f5d83b4f7a1585bac9e7656d6af46183262 (diff) | |
| parent | 6ce71c56d6affb57a3537a2732485a4918306d4b (diff) | |
Merge remote-tracking branch 'upstream/master'
Diffstat (limited to 'dynamic-programming.html.markdown')
| -rw-r--r-- | dynamic-programming.html.markdown | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/dynamic-programming.html.markdown b/dynamic-programming.html.markdown index 7df367e7..4db8e92e 100644 --- a/dynamic-programming.html.markdown +++ b/dynamic-programming.html.markdown @@ -26,7 +26,7 @@ The Longest Increasing Subsequence problem is to find the longest increasing sub First of all we have to find the value of the longest subsequences(LSi) at every index i with last element of sequence being ai. Then largest LSi would be the longest subsequence in the given sequence. To begin LSi is assigned to be one since ai is element of the sequence(Last element). Then for all `j` such that `j<i` and `aj<ai`, we find Largest LSj and add it to LSi. Then algorithm take *O(n2)* time. Pseudo-code for finding the length of the longest increasing subsequence: -This algorithms complexity could be reduced by using better data structure rather than array. Storing predecessor array and variable like largest_sequences_so_far and its index would save a lot time. +This algorithms complexity could be reduced by using better data structure rather than array. Storing predecessor array and variable like `largest_sequences_so_far` and its index would save a lot time. Similar concept could be applied in finding longest path in Directed acyclic graph. |