Lexi's Leetcode solutions

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

Posted on: October 3, 2013

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;
}
Advertisements
Tags: ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: