CodeBarn
8/13/2018 - 12:07 AM

Longest Increasing/Decreasing Subsequence

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);
    }
  }
}