Exercises — DP problems — Longest Increasing Subsequence (LIS) — O(n²) and O(n log n)

A valid increasing subsequence must (1) appear in the same left-to-right order using original positions, and (2) be strictly increasing.

• (a) [3,4,5,9] — positions 0,2,4,5, values rise 3<4<5<9. ✅
• (b) [1,4,5,2,6] — values are not increasing (5 then 2 goes down). ❌
• (c) [3,4,5,6] — positions 0,2,4,7, all in order, 3<4<5<6. ✅
• (d) [1,1,5,9] — 1 is not < 1, equal values break strict increase. ❌

Valid: (a) and (c).

dp = [1,2,2,3], answer = 3 (e.g. [2,5,7] or [2,3,7]).

dp = [1,2,1,1,2,3], answer = 3. Trace back from dp[5]=3: 9 came from index 4 (8, dp 2), which came from index 0 or 2 or 3 (4 or 3, dp 1). One optimal: [4, 8, 9] (indices 0,4,5) or [3,8,9].

Use lower_bound (leftmost tails[k] >= x); replace, else append.

Length = 4 (e.g. [2,3,4,10] or [1,3,4,6]). See the pile figure below.

Key idea: a decreasing subsequence of A is an increasing subsequence of the reversed comparison. Two clean tricks, both give the same length:

• Negate every value: B = [-5,-1,-6,-2,-7,-3], then run LIS on B.
• Or reverse A and run longest decreasing = LIS of reversed if you flip sign; simplest is the negation trick.

Run LIS (patience) on B = [-5,-1,-6,-2,-7,-3]:

Length = 2. Check on original: decreasing pairs like [5,1], [6,2], [7,3] — length 2, and no length-3 decreasing chain exists (the array keeps jumping back up). ✅

• $O(n^2)$: the inner loop over $j<i$ does about $\frac{n(n-1)}{2}\approx \frac{n^2}{2}=5\times 10^{11}$ comparisons. Far too many for a second of runtime.
• $O(n\log n)$: each of $n$ elements triggers one binary search over tails (length $\le n$), costing $\lceil {\log }_{2}n\rceil$ comparisons. Here ${\log }_2(10^6)\approx 20$, so about $n{\log }_{2}n\approx 2\times 10^7$ comparisons.
• Ratio $\approx \frac{5\times 10^{11}}{2\times 10^7}=25,000\times$ faster. The $n^2$ term dominates and is why we replace the linear scan for a predecessor with a binary search.

Extend the DP with a second array cnt[i] = number of LIS ending at i. Rule: for each i, over all j<i with A[j]<A[i]:

• if dp[j]+1 > dp[i]: set dp[i]=dp[j]+1, cnt[i]=cnt[j] (found a strictly longer way — reset the count).
• if dp[j]+1 == dp[i]: cnt[i] += cnt[j] (another way of the same best length).

Length = 4, number of LIS = 2: [1,3,5,7] and [1,3,4,7]. ✅

Reframe: whatever you keep must be a strictly increasing subsequence, so keeping the maximum means keeping an LIS. Minimum deletions $=n-\text{LIS length}$. Run LIS on A = [4,3,6,5,8,7]:

LIS length = 3 (e.g. [3,5,7] or [4,6,8]). $n=6$, so minimum deletions $=6-3=3$. ✅

The trick: sort by width ascending, and for ties in width, sort height descending. Then run plain LIS on the heights.

• Why width asc: nesting requires increasing width, so process envelopes left to right in width order.
• Why height descending on equal widths: two envelopes of the same width can never nest (width not strictly larger). Sorting their heights descending guarantees at most one of them is picked by the height-LIS, because a descending run can't be an increasing subsequence.

Sort: widths 2,5,6,6. The two width-6 envelopes get heights 7,4 sorted descending: [[2,3],[5,4],[6,7],[6,4]]. Heights sequence: [3, 4, 7, 4]. Run LIS on [3,4,7,4]:

LIS = 3. Answer = 3: [2,3] ⊂ [5,4] ⊂ [6,7]. ✅

Why it works: an increasing subsequence of A is a subsequence that also appears, in the same order, inside the sorted list of A's distinct values. The longest common one to both is exactly the LIS. We use sorted-unique so equal values can't be matched twice (that keeps it strictly increasing).

• A = [3,1,2,1,3], sorted-unique(A) = [1,2,3].
• LCS of [3,1,2,1,3] and [1,2,3]: the common increasing run 1,2,3 — take the first 1 (index 1), 2 (index 2), 3 (index 4). Length 3.
• Direct LIS of A: [1,2,3] → length 3. ✅ They match.