Editorial for Longest Increasing Subsequence

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Let $dp_i$ ~dp_i~ be the length of the longest increasing subsequence that ends exactly at position $i$ ~i~.

For each earlier position $j < i$ ~j < i~, if $a_j < a_i$ ~a_j < a_i~, then we can append $a_i$ ~a_i~ after a subsequence ending at $j$ ~j~. Therefore, $dp_i$ ~dp_i~ is one more than the maximum valid $dp_j$ ~dp_j~, or $1$ ~1~ if no earlier value can come before $a_i$ ~a_i~.

The answer is the maximum value among all $dp_i$ ~dp_i~. Equal values cannot extend each other because the subsequence must be strictly increasing.

Time complexity is $O(n^2)$ ~O(n^2)~.

Solution (Python)

n = int(input())
a = list(map(int, input().split()))

dp = [1] * n
answer = 1

for i in range(n):
    best = 1
    ai = a[i]
    for j in range(i):
        if a[j] < ai:
            best = max(best, dp[j] + 1)
    dp[i] = best
    answer = max(answer, best)

print(answer)

Comments

There are no comments at the moment.