[classic] Longest Increasing Subsequence |最大增长子数列（可以不连续）

Posted by: lexigrey on: October 3, 2013

• In: classic
• Leave a Comment

DP是O(n2)的解法。新开一个数列B，B[i]表示以A[i]结尾的LIS的最大长度。每次在i处往前看，若j<i，则以i结尾的就只少>=B[j] + 1。

public int getLIS(int[] A) {
  int[] B = new int[A.length];
  int max = 1;
  B[0] = 1;
  for (int i = 1; i < A.length; i++) {
    B[i] = 1;
    for (int j = i - 1; j >= 0; j--) {
      if (A[i] > A[j]) {
        B[i] = Math.max(B[i], B[j] + 1);
        max = Math.max(B[i], max);
      }
    }
  }
  return max;
}

Tags: 1WayDP, array