## ยง 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.