Longest Increasing Subsequence

Medium#3001d array

You get an array of numbers. Pick some of them, keeping their order, so that each picked number is larger than the one before; the numbers need not stand side by side. How many can you pick at most? Our example: [4, 9, 5, 2, 6, 7, 3] — 4, for example 4, 5, 6, 7.

300 Longest Increasing SubsequenceWalkthrough · 1×

Example: [4, 9, 5, 2, 6, 7, 3]. Watch 6 at index 4: it grows from the 5 two places back, not from the 2 next to it.

numslis041925324657631111111
i: this numberfilledj: smaller, can come beforej: not smaller, or no longeranswer and its chain

lis[i]: the longest increasing chain that ends at nums[i]. Each number alone is a chain of 1

01/29
restart · back · play · step
Speed
1function lengthOfLIS(nums):
2 lis = array of size len(nums), all 1
3 for i from 1 to len(nums) - 1:
4 for j from 0 to i - 1:
5 if nums[j] < nums[i]:
6 lis[i] = max(lis[i], lis[j] + 1)
7 return max(lis)
state
lis
[1, 1, 1, 1, 1, 1, 1]
i
–
j
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. 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].
  2. 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.
  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 ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.