LIS/LDS; DP, O(n^2)
// DP N^2 to find and store length of longest ascending subsequence
for (int i = n - 1; i >= 0; i--) {
asc[i] = 1;
for (int j = i + 1; j < n; j++) {
// less than, for ascending subseq
if (A[i] < A[j]) {
asc[i] = max(asc[i], asc[j] + 1);
}
}
}
for (int i = n - 1; i >= 0; i--) {
desc[i] = 1;
for (int j = i + 1; j < n; j++) {
// greater than, for descending subseq
if (A[i] > A[j]) {
desc[i] = max(desc[i], desc[j] + 1);
}
}
}