Editorial for Longest Increasing Subsequence

Approach

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

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

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

Time complexity is $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)