LCS, LIS, knapsack and subset DP | DSA

← BlogDATA STRUCTURES / ALGORITHMSPython example pack ↓

LCS dp[i][j] measures the longest common subsequence of two prefixes. Matching final characters use diagonal+1; otherwise take top/left maximum. A subsequence need not be contiguous; substring is a different problem.

One-dimensional0/1 knapsack must iterate capacities backward or it may reuse the current item. LIS tails[i] is the smallest achievable ending value for lengthi+1, not necessarily an actual subsequence; parent indices reconstruct one.

Subset DP uses a visited mask and endpoint, as in TSP. Tree DP merges child states; DAG DP uses topological order. Knuth, divide-and-conquer and convex-hull optimisations need proven structural conditions, not just a slow recurrence.

A worked trace

[3,1,2,5,4] yields tails [3]→[1]→[1,2]→[1,2,5]→[1,2,4], giving length3; lower_bound enforces strict increase.

Cost and assumptions

LCS O(nm); LIS O(n log n);0/1 knapsack O(nW); subset TSP O(n²2ⁿ).

Executable example

Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.

Python 3

from bisect import bisect_left

def lis_length(a):
    tails=[]
    for x in a:
        i=bisect_left(tails,x)
        if i == len(tails): tails.append(x)
        else: tails[i]=x
    return len(tails)
assert lis_length([3,1,2,5,4]) == 3
assert lis_length([2,2,2]) == 1

TEST YOUR UNDERSTANDING

Your turn

What replaces bisect_left for nondecreasing LIS?

Reveal the reasoning

bisect_right places equal values to the right. Strict versus nonstrict ordering changes the boundary rule.

Take it further

Write down the input contract and the invariant before changing the example.
Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
Derive the cost under the stated model; measure several input sizes and explain discrepancies.

Primary reading & lecture notes

Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.

MIT 6.006 · Introduction to Algorithms ↗MIT 6.046J · Design and Analysis ↗

Solve the exercise before moving on.

RasimAtaberkŞahin