Click here to see the full article post
The English is hard to understand. Please paraphrase. For example, in Solution 3, please clearly say "dp[i] represents the longest subsequence ending exactly at i.".
@kenteng Completely agree with you!
For example, if the inputs nums is [4, 10, 4], the solution builds the following dp:
[1, 2, 1]
Note: dp array does not result in longest increasing subsequence, but length of dpdp array will give you length of LIS.
This sentence makes me completely understands the binary dp solution.Thanks very much!
Does this O(2^n) approach make sense ? Why simply use two loop O(n^2) for brute force? We can find all LIS start with every element in 2 loops. Am I right ?
@danielz You don't simply compare two elements in each iteration. Think it in another way, the largest possible total number of the combination of the LIS is 2^n, and thus, the brute force takes O(2^n) to finish.
Nice explanation. I liked the last approach, but using last approach my submission time is 3ms. I replaced Arrays.binarySearch() with my own implementation of binary search and my time improved to just 1ms. Reason: Arrays.binarySearch() library method is optimized for large inputs, so for smaller inputs library uses insertion sort algo rather than binary search.
Wow, I love the last solution. Who figured this out/what was the intuition?
I kind of have to agree with previous comments about the language used to write this article. A lot Leetcode articles (like this one) attempt to use really formal English, but (I think) because the author is obviously not a native English speaker, it makes the article even harder to understand.
I just resort to looking at the code first, in order to understand the written explanation, where I think the goal should be the opposite.
If the author is not a native english speaker, or a native speaker can't thoroughly edit the article, I suggest just writing it in casual English, which would be easier for everyone. More people would understand and get more out of the article.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.