Hard · DP

Longest Increasing Subsequence

A subsequence skips elements but keeps their order — of 10 9 2 5 3 7, the chain 2 3 7 is legal and 3 2 is not. Define best[i] as the longest rising chain that ends exactly at position i, and every element only needs to ask: who before me was smaller, and how long was their best chain?

At a glance<code>best[i] = 1 + max(best[j])</code> over j < i with <code>a[j] < a[i]</code> (else 1); the answer is the maximum over all i — an O(n²) double loop.

Problem

Input: The first line is n (1 ≤ n ≤ 500). The second line has n integers (−1000 to 1000).

Output: The length of the longest strictly increasing subsequence.

Samples:

Input	Output
`8 10 9 2 5 3 7 101 18`	`4`
`4 2 2 2 2`	`1`

In the first sample the answer 4 is the chain 2, 3, 7, 18 (or 2, 5, 7, 18). The second sample is the strictness detector: equal neighbors cannot chain, so four 2s give length 1, not 4.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Pin the ending position

"Longest increasing subsequence" is slippery until you pin where it ends. best[i] = longest chain ending exactly at i turns the vague goal into n precise sub-questions — and the real answer is simply the largest of them. This "best ending here" move is the same one that cracked Maximum Subarray Sum.

Hint 2 — Every element starts at 1

Before any comparison, best[i] = 1: the element alone is a chain of length one. Then improve it with the best smaller predecessor. Two classic bugs cancel this base: forgetting to set it (reading the uninitialized global — this engine does not zero arrays), or starting best[i] at 0 so a chain never counts its own last element.

Hint 3 — Strict means strict

The comparison is a[j] < a[i], not <=. With equal neighbors allowed, the all-equal test returns n instead of 1 — the judge's second sample exists precisely to catch this one character.

Solution (try it first!)

#include <iostream>
using namespace std;

int a[505], best[505];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 0;
    for (int i = 0; i < n; i++) {
        best[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && best[j] + 1 > best[i]) {
                best[i] = best[j] + 1;
            }
        }
        if (best[i] > ans) ans = best[i];
    }

    cout << ans << endl;
    return 0;
}

The O(n²) double loop is the honest version; an O(n log n) upgrade exists that keeps, for each chain length, the smallest possible tail — and it needs Binary Search to place new elements. Between the two, notice what did not change: the definition of best[i]. Better algorithms rarely replace a DP's meaning; they make the same meaning cheaper to consult.

Deep dive

Why this works

Pin the end: best[i] = longest strictly increasing chain ending exactly at i. Every i then scans its entire past for smaller elements with the best chains — O(n) predecessors each, O(n²) total — and the global answer is the max over all endings. The 'best ending here' framing is what makes the vague goal computable.

The cost

O(n²) time, O(n) space — 500² = 250,000 comparisons, instant. The O(n log n) upgrade keeps per-length smallest tails and binary-searches insertions, but the DP definition survives unchanged.

Where it goes wrong

a[j] <= a[i] instead of strict <: the all-equal test returns n instead of 1 — one character, one wrong answer.
Forgetting best[i] = 1 before the scan: on this engine the global is garbage, and even on real compilers the base case is what lets a chain start anywhere.
Reporting best[n-1] instead of the max over all i: the longest chain may end anywhere (see the descending test, where it ends at position 0).

Next step

The same 'ending here' DP in one dimension without pairs: Maximum Subarray Sum. The speed upgrade needs Binary Search over chain tails.

Two things to remember

best[i] = 1 + best of smaller predecessors; answer = max over endings.
Strict < vs <= is the whole difference between distinct and sorted.

🐞 This version fails — open it and try

Uses a[j] <= a[i] — equal neighbors chain, so all-2s gives 4 instead of 1

#include <iostream>
using namespace std;

int a[505], best[505];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        best[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] <= a[i] && best[j] + 1 > best[i]) {   // bug: not strict
                best[i] = best[j] + 1;
            }
        }
        if (best[i] > ans) ans = best[i];
    }
    cout << ans << endl;
    return 0;
}