§ 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.