Longest Bitonic Subsequence
A bitonic sequence is first strictly increasing, then strictly decreasing — either part may be empty. Given A[0..n−1], find the length of the longest bitonic subsequence: keep the order, drop whatever you like.
A = [−78, 117, 131, −136, 182, −96, −23, −97, −200, 49] → 7 (−78, 117, 131, 182, −23, −97, −200)
int bitonic(const vector<int>& A);
1 ≤ n ≤ 2000 · −256 ≤ A[i] ≤ 255
Follow the recipe (slide 8)
- Subproblem ①. Define Inc[i] in one precise sentence.
hint
Inc[i] = the length of the longest strictly increasing subsequence of A[0..i] that ends at i. This is exactly the LIS table from slide 9.
- Subproblem ②. Now define Dec[i], the mirror image looking right.
hint
Dec[i] = the length of the longest strictly decreasing subsequence of A[i..n−1] that starts at i.
- Recurrence. A bitonic subsequence has a peak. If the peak is
A[i], how long is the best subsequence through it? And the final answer?
hint
A peak at i gives Inc[i] + Dec[i] − 1 (the peak is counted twice). The answer is the max over all i. A purely increasing or purely decreasing array is also bitonic — one of the two parts is just empty.
- Table + order. Which direction does each table fill, and why?
hint
Inc[i] depends on Inc[j] for j < i: fill left to right. Dec[i] depends on j > i: fill right to left. Then one loop takes the max.
- Analyze. Running time and space?
hint
O(n²) time, O(n) space. The n = 2000 test runs in well under a second.
Going further
- Print an actual longest bitonic subsequence: keep a backpointer like B[i] for each table (slide 9), then walk back from the best peak.
- Suppose "increasing" means non-decreasing. Which comparisons change? Give an array where the answer differs.
- Can you compute the Inc table in O(n log n) (patience sorting)? Then the whole problem is O(n log n).
Palindrome Partition
Any string can be cut into palindromes: bubbaseesabanana = bub · baseesab · anana. Find the minimum number of palindromic pieces that make up s[0..n−1].
s = "bubbaseesabanana" → 3 (bub · baseesab · anana)
int minPal(const string& s);
1 ≤ n ≤ 2500 · lowercase letters 'a'–'z'
Follow the recipe (slide 8)
- Try greedy first. Repeatedly cut the longest palindrome at the front. Run the tests. What happens on greedy trap?
hint
For aaba the longest prefix palindrome is aa, so greedy needs 3 pieces; the best is a · aba. Taking the best piece now can ruin the rest — the same trap as in coin change (slide 12).
- Subproblem. Define P[i] in one precise sentence.
hint
P[i] = the minimum number of palindromes that partition the prefix s[0..i−1]. The answer is P[n].
- Recurrence. Look at the last piece of an optimal partition of
s[0..i−1]; say it is s[j..i−1]. What must hold, and what is left?
hint
If s[j..i−1] is a palindrome:
P[i] = 1 + min { P[j] : 0 ≤ j < i, s[j..i−1] palindrome }, with P[0] = 0. The one-letter piece j = i−1 always works, so P[i] ≤ i.
- Palindrome lookup. Don't re-scan each candidate piece. Fill a table
isPal[j][k] first: how does isPal[j][k] relate to a smaller subproblem?
hint
isPal[j][k] = (s[j] == s[k]) && (k − j < 2 || isPal[j+1][k−1]). Fill by increasing substring length. After that the main loop is O(1) per piece.
- Analyze. Time and space?
hint
O(n²) time and O(n²) space for the table; the partition DP adds only O(n²) time and O(n) space.
Going further
- Print one optimal partition: remember the
j that achieved each minimum P[i], then walk back from n.
- Count the number of minimum partitions of
s.
- The table needs O(n²) memory. Can you compute P with O(n) extra space (expand around centers)?