Lesson 8 Longest Increasing Subsequence (LIS)

Problem

Given an array:

[10, 9, 2, 5, 3, 7, 101, 18]

Find the length of the Longest Increasing Subsequence (LIS).

Example:

2
5
7
101

Length:

4

Another valid LIS:

2
3
7
18

Also has length:

4

---

Subsequence vs Subarray

Subsequence

• Order must be preserved.

• Elements may be skipped.

Example:

2 5 3 7

Valid subsequences:

2 5 7
2 3 7
5 7

---

Subarray

Elements must be contiguous.

Example:

5 3 7

is a subarray.

---

State Design

Define:

dp[i]

Meaning:

Length of the longest increasing subsequence
ending exactly at index i.

Important wording:

ending exactly at i

This is similar to Kadane’s Algorithm.

---

State Interpretation

Example:

nums = 2 5 3 7

For:

dp[3]

Meaning:

Longest increasing subsequence
ending at value 7.

Possible predecessors:

2 -> 7
5 -> 7
3 -> 7

The best predecessor determines the answer.

---

Transition

For every previous index:

j < i

If:

nums[j] < nums[i]

then the subsequence ending at j can be extended.

Candidate:

dp[j] + 1

Take the maximum candidate.

Recurrence:

dp[i]
=
1 + max(dp[j])
 
for all
j < i
where nums[j] < nums[i]

If no previous value is smaller:

dp[i] = 1

The element starts a new increasing subsequence.

---

Base Case

Every single element is an increasing subsequence.

Therefore:

dp[i] >= 1

Initially:

dp[i] = 1

for all i.

---

Example

Array:

2   5   3   7

Compute:

dp[0] = 1
 
dp[1]
= 1 + dp[0]
= 2
 
dp[2]
= 1 + dp[0]
= 2
 
dp[3]
= 1 + max(dp[0], dp[1], dp[2])
= 1 + max(1,2,2)
= 3

Result:

nums: 2 5 3 7
dp:   1 2 2 3

Longest Increasing Subsequence:

2 5 7

or

2 3 7

Length:

3

---

Final Answer

Because:

dp[i]

means:

Best increasing subsequence
ending exactly at i.

The best subsequence may end anywhere.

Therefore:

Answer = max(dp)

not:

dp[n-1]

---

Comparison with Kadane

Kadane

State:

dp[i]
=
Maximum subarray sum ending exactly at i.

Transition:

max(
    nums[i],
    dp[i-1] + nums[i]
)

Only depends on:

dp[i-1]

---

LIS

State:

dp[i]
=
Longest increasing subsequence ending exactly at i.

Transition:

1 + max(dp[j])

for all valid previous indices.

May depend on:

dp[0]
dp[1]
...
dp[i-1]

---

New DP Pattern

Previous lessons:

Fibonacci
House Robber
Coin Change
Kadane

Each state depended on only one or two previous states.

LIS introduces:

One state may depend on many previous states.

General pattern:

for each state i
 
    examine every earlier state
 
    choose the best transition

This pattern appears in many DP problems.

---

Key Lessons

• The DP state represents a subproblem, not an array position.

• The state definition determines where the final answer is stored.

• A state may depend on all previous states, not just neighboring ones.

• Always ask:

  1. What does dp[i] mean?

  2. Which previous states can transition to dp[i]?

  3. Where is the final answer stored?

For LIS:

State:
    Best increasing subsequence ending at i
 
Transition:
    Extend the best valid previous subsequence
 
Answer:
    max(dp)