CodeBarn
8/13/2018 - 12:07 AM

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