## § Longest Convex Subsequence DP

• This was an enlightening problem to solve due to the presence of many degenerate cases.
• The question: given an array xs[], find the length of the longest subsequence ys[] such that for all indexes 0 <= l < m < r < |ys|, we have that 2*ys[m] < ys[l] + ys[r].
• Key DP idea: dp[maxm][maxr] is the length of the longest convex subsequence with penultimate index <= maxm and final index <= maxr.
• The bare recurrence (without thinking about base cases) can be implemented as follows:
int f(vector<int> &xs) {
const int n = xs.size();
vector<vector<int>> dp(n, vector<int>(n, 0));

for (int r = 0; r < n; ++r) {
for (int m = 0; m < r; ++m) {
for (int l = 0; l < m; ++l) {
if (2 * xs[m] < xs[l] + xs[r]) {
dp[m][r] = max<int>(dp[m][r], 1 + dp[l][m]);
}
}
}
}

return ???;
}

• The "problem" is to deal with the degenrate cases where the array has only length 0, length 1, or length 2 when the DP conditions don't kick in. How does one implement these neatly?
• The insight is to see that at each location in the program, we have a lower bound on the best DP value we can achieve. For example, at the beginning, we know that best >= 0. When we enter into the loop of r, we know that we have at least one element, so best >= 1, and so on. If we insert these lower bounds systematically into the code, we arrive at:
int f(vector<int> &xs) {
const int n = xs.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
int best = 0;

for (int r = 0; r < n; ++r) {
ATLEAST1: best = max<int>(best, 1);
for (int m = 0; m < r; ++m) {
ATLEAST2: best = max<int>(best, 2);
dp[m][r] = 2;
for (int l = 0; l < m; ++l) {
if (2 * xs[m] < xs[l] + xs[r]) {
dp[m][r] = max<int>(dp[m][r], 1 + dp[l][m]);
}
best = max<int>(best, dp[m][r]);
}
}
}

return best;
}

• We see that whenever we "learn" more information, we increase best, possibly without being able to even initialize dp[.][.]! This happens for example at ATLEAST1:, where we have one element so we know that best >= 1, but we don't have two elements to initialize the DP array.