Algoritmalar
en

Longest Increasing Subsequence

Dynamic Programming O(n²) O(n)

Longest run of values that strictly increases (not necessarily contiguous), via dp[i] = best subsequence ending at i.

dp = length of LIS ending at each value
a109253710118
dp1·······
1/55

dp[0] = 1 — value 10 on its own.

Invariantdp[i] is the longest increasing run ending exactly at i.

lis.c
int lis(int a[], int n) {
    int dp[n];
    int best = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        }
        if (dp[i] > best) best = dp[i];
    }
    return best;
}

How Longest Increasing Subsequence works

dp[i] = length of the longest increasing run ending exactly at i. For each i, look back at every smaller element and extend its best run. The answer is the maximum over all endings.

Worst case

O(n²) as shown; an O(n log n) patience-sorting variant exists.

When to use it

Longest trend detection, patience sorting, box-stacking style problems.