Why it works
- Any increasing chain that ends at nums[i] and has more than one number has a number just before nums[i], some smaller nums[j] with j < i. Cut nums[i] off and what is left is a chain ending at nums[j], at most lis[j] long. So lis[i] = 1 + the largest such lis[j].
- That j can be anywhere before i, so every earlier number is checked, not just the neighbour: for 6 the 2 right before gives 2, the 5 two places back gives 3.
- The best chain can end anywhere, so the answer is the largest cell, not the last one: here lis ends with 2 while the chain 4, 5, 6, 7 ends at index 5.
Complexity
Time O(n²): every number looks at every number before it once. Memory O(n): one cell per number. A faster O(n log n) way keeps the smallest end of a chain of each length and finds the place for each number with binary search.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗