Two chains meeting at a peak
Run the increasing-chain table forward and backward, then find where the two halves add up highest. About 13 minutes.
Up the mountain, then down
A trekking route climbs to a peak and then descends. Given a list of heights, what's the longest route you can pick, keeping the order, that strictly rises to one peak and then strictly falls? A route that only rises or only falls counts too.
You've already solved half of this. The rising half is the longest rising chain ending at the peak.
Solve it twice, then meet at the peak
Work out, for every number, the longest rise that ends on it, scanning from the left. Then do the mirror image: the longest fall that starts on it, scanning from the right.
Now try every number as the peak. Its route is the rise plus the fall, minus 1, because the peak itself is in both halves. The best of those is the answer: 6 in the example, like 1, 2, 10, 4, 2, 1.
inc, dec = [1] * n, [1] * n
The rise: for each number, the longest rising chain that ends on it, scanning from the left (the table from the first step).
The longest rise ending on a number is 4 long, and the longest fall starting on it is 3 long. How long is the mountain with that number as the peak?
- A6
- B7
- C4
Show the answer
6. 4 + 3 − 1 = 6. The peak belongs to both halves, so it's counted once.
Longest bitonic subsequence
Given an array of integers nums, return the length of the longest bitonic subsequence — one that strictly increases up to some peak value, then strictly decreases. A purely increasing or purely decreasing subsequence counts (the peak can be the first or last element of the subsequence).
nums = [1, 11, 2, 10, 4, 5, 2, 1] → 6
0 ≤ n ≤ 1,000 · −1,000,000,000 ≤ each value ≤ 1,000,000,000