{"id":319,"date":"2020-12-24T18:30:28","date_gmt":"2020-12-24T18:30:28","guid":{"rendered":"https:\/\/www.canosielabs.com\/blog\/?p=319"},"modified":"2020-12-24T18:30:30","modified_gmt":"2020-12-24T18:30:30","slug":"longest-increasing-subsequence","status":"publish","type":"post","link":"https:\/\/www.canosielabs.com\/blog\/longest-increasing-subsequence\/","title":{"rendered":"Longest Increasing Subsequence"},"content":{"rendered":"\n

Today we’re going to look at Longest Increasing Subsequence<\/a> and we’re going to focus on providing the O(n2<\/sup>) solution. While there is a faster O(nlog(n)) solution, the O(n2<\/sup>) solution is more initiative and provides more learning for future problems you may see on interviews.<\/p>\n\n\n\n

To understand the intuition behind the problem, you need to make note of a few things. Consider the input nums=[6, 7, -2, 0, 8, 2, 3]<\/code><\/p>\n\n\n\n

1.<\/strong> The longest increasing subsequence in 0...i<\/code> is one plus the lonest increasing subsequence that exists for all valid sequences possible in the range 0...j<\/code> where j<i <\/code>and<\/strong> the last number of the sequence is less than nums[i].<\/p>\n\n\n\n

In our example, the longest sequence at i=4 <\/code>(nums[4] = 8<\/code>) is the longest sequence that exists in the subset of nums 0...i-1<\/code> ([6, 7, -2, 0]<\/code>) and where the last number in the sequence is less than 8. In this case, the longest sequence is [6, 7].<\/p>\n\n\n\n

2. <\/strong>We can always add a new number to the end of a sequence if that number is greater than the last number of the sequence. <\/p>\n\n\n\n

\nThus, to get the longest subsequence for a input nums[0…i], we need take the longest subsequence that can be generated for the subsets:
\nnums[0, 1]
\nnums[0, 2]
\n…
\nnums[0, i-1]
\n
but we can only consider the subsets where the last number is less than nums[i]. If it was a higher number, the subsequence would not be strictly increasing. \n<\/p>\n\n\n\n

And by fact #1, once we found a subsequence nums[0, j] that gives us the longest subsequence, we can make a even longer subsequence by adding nums[i] to the end.<\/p>\n\n\n\n

Let’s denote f(nums, i) = the longest subsequence length for nums from index 0 to i. To run the algorithm above, we are going to be executing f(nums, i) <\/strong>for many times with the same value of i and ii)<\/strong> we’re also breaking the problem f(nums, i) to subproblems max (f(nums, 1), f(nums, 2)…f(nums, i-1)) considering the optimal solution to each subproblems in our final problem. This sounds like dynamic programing.<\/p>\n\n\n\n

DP Table<\/h2>\n\n\n\n

The DP table is of length 0 <\/strong>to nums.length<\/strong>, where each position i keeps track of the longest subsequence length using a subset of nums, nums[0, i]<\/strong>. <\/p>\n\n\n\n

Tabulation<\/h2>\n\n\n\n
\tpublic int lengthOfLIS(int[] nums) {\n\n\t\tint[] memo = new int[nums.length];\n\t\tArrays.fill(memo, 1);\n\n\t\tif (nums.length == 1) {\n\t\t\treturn 1;\n\t\t}\n\n\t\tfor (int i = 1; i < nums.length; i++) {\n\n\t\t\tfor (int j = 0; j < i; j++) {\n\t\t\t\tif (nums[j]  memo[i]) {\n\t\t\t\t\tmemo[i] = memo[j] + 1;\n\t\t\t\t}\n\t\t\t}\n\n\t\t}\n\t\n\t\tArrays.sort(memo);\n\t\treturn memo[memo.length-1];\n\t}<\/code><\/pre>

\n\n\n\n
Conclusion<\/h2>\n\n\n\n
I’ve decided the keep the source code fairly verbose in order to maintain readability.  While there are more efficient methods (to the O(n2<\/sup>) solution provided above, I believe it’s better (in terms of interview preparation) to write readable solutions in order to form key takeaways then to confuse people wile saving a small amount of memory.<\/p>\n\n\n\n
As mentioned above, there is a more efficient O(nlong) solution, but we won’t cover that today.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today we’re going to look at Longest Increasing Subsequence and we’re going to focus on providing the O(n2) solution. While there is a faster O(nlog(n))…<\/p>\n","protected":false},"author":3,"featured_media":255,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[11],"tags":[10],"class_list":["post-319","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-coding-questions","tag-coding-questions"],"_links":{"self":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/319","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/comments?post=319"}],"version-history":[{"count":6,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/319\/revisions"}],"predecessor-version":[{"id":326,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/319\/revisions\/326"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media\/255"}],"wp:attachment":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media?parent=319"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/categories?post=319"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/tags?post=319"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}