Increasing Subsequence (LIS)

The Longest Increasing Subsequence (LIS) problem is a classic dynamic programming challenge. While the problem seems straightforward, finding the longest increasing subsequence in a list of integers, many learners (including myself) get confused by why we look backward, how the recurrence works, and how to recover the actual sequence.

Given an array of integers nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

Example:

Input: nums = [10, 9, 2, 5, 3, 7, 101]Output: 4Explanation: The longest increasing subsequence is [2, 3, 7, 101].

Why Not a Greedy Approach?

One might think to just keep picking the next number that's greater than the current. But consider this:

nums = [3, 4, 2, 5]

A greedy approach might pick [3, 4, 5], missing the better [2, 5] that starts from a smaller number.

We need to check all valid previous options, which hints at dynamic programming.

The DP Insight

Let:

- dp[i] = length of the longest increasing subsequence that ends at index i

DP Recurrence:

dp&#91;i] = max(dp&#91;j] + 1 for all j < i where nums&#91;j] < nums&#91;i])

If no such j exists, then dp[i] = 1 (the number by itself).

This means: at each i, we look backward and find the longest subsequence we could extend using nums[i].

Step-by-step Example:

Given:

nums = &#91;10, 9, 2, 5, 3, 7, 101]

We initialize:

dp = &#91;1, 1, 1, 1, 1, 1, 1] # Every number is a subsequence of length 1 by itself

Then we iterate:

- At index 3 (nums[3] = 5), we can extend LIS from 2 (at index 2):dp[3] = dp[2] + 1 = 2

- At index 5 (nums[5] = 7), we can extend from 2 → 3 → 7:dp[5] = dp[4] + 1 = 3

Final dp becomes:

dp = &#91;1, 1, 1, 2, 2, 3, 4]

So the length of LIS is max(dp) = 4.

def lengthoflis(nums):
if not nums:
return 0

n = len(nums)
dp = &#91;1] * n

for i in range(1, n):
for j in range(i):
if nums&#91;j] < nums&#91;i]:
dp&#91;i] = max(dp&#91;i], dp&#91;j] + 1)

return max(dp)

This dynamic programming method runs in:

- Time: O(n²)

- Space: O(n)

For large arrays (e.g. 10,000+ elements), this can be slow. There exists a faster O(n log n) method using binary search with greedy placement. However, that method only gives the length, not the full sequence (without extra tricks).