Longest run-up-then-run-down in prices

Question

A "bitonic" pattern rises strictly to a single peak and then falls strictly. Given daily prices, find the length of the longest bitonic subsequence (days need not be consecutive), a stylized momentum-then-reversal move.

prices = [1, 4, 7, 2, 5, 3, 1]
-> 6        # 1, 4, 7, 5, 3, 1

Return the length of the longest bitonic subsequence in O(n^2) time.

Accepted Answer

For each index compute two things: inc[i], the longest strictly increasing subsequence ending at i, and dec[i], the longest strictly decreasing subsequence starting at i. Any index can serve as the peak, contributing inc[i] + dec[i] - 1 (the peak is shared by both halves, so subtract one). Take the maximum over all peaks. At the peak 7 (index 2), inc = 3 (1,4,7) and dec = 4 (7,5,3,1), giving 3 + 4 - 1 = 6. Time O(n^2), space O(n). Edge cases: a strictly monotonic series has one "half" of length 1, so the answer is just its length; requiring both a genuine rise and fall means enforcing inc[i] …

Longest run-up-then-run-down in prices

Your answer

More Coding questions