Practice45 min
Practice: Subsequences & Partitions
Sign-flip products, dictionary segmentation, LIS, and subset-sum to half.
Four medium DPs with distinctive states: track max and min products together, segment against a dictionary, the classic O(n squared) LIS, and reduce equal partitioning to subset-sum on half the total.
Problems0 of 4 solved
- Not startedMaximum Product Subarraytrack running max and min products (sign flips)medium
- Not startedWord BreakDP over prefixes with dictionary lookupmedium
- Not startedLongest Increasing SubsequenceO(n^2) DP (or patience sorting + binary search)medium
- Not startedPartition Equal Subset Sumsubset-sum DP to half of totalmedium