Leetcode 300题，最长递增子序列，如何求解？

本文共计503个文字，预计阅读时间需要3分钟。

1. 最长递增子序列：思路是dp，先说一个很general的idea。子问题dp[i]表示以array[i]为结尾的最长子序列的长度。那么只需要遍历之前所有的dp值，取最大值即可。复杂度复杂度。

1.最长递增子序列：

思路是dp，先说一个很general的idea。子问题为dp[i]，以array[i]为结尾的最长子序列的最后一个元素。那么只要遍历之前的所有dp即可，取可行的里面的最大值。复杂度On2.

public int maxISLength(int[] array){
int[] dp = new int[array.length];
dp[0] = 1;
int max_len = 0;
for(int i = 1; i < array.length; i++){
int max = 0;
for(int j = 0; j < i; j++){
if(array[i] > array[j])
max = Math.max(dp[j] + 1, dp[i]);
}
dp[i] = max;
max_len = Math.max(max_len, dp[i]);
}
return max_len;
}

不过有一个更吊的，时间Onlogn。因为使用了二分。子问题不同，dp[i]为长度为i的子序列的最后一元素。那么对于任何一个元素array[i]，二分的insertPos就是其所在的子序列的长度。

public int maxISLengthB(int[] array){
if(array == null || array.length == 0) return 0;
int len = 1;
int[] dp = new int[array.length + 1];
dp[1] = array[0];
for(int i = 1; i < array.length; i++){
int r = Arrays.binarySearch(dp, 1, 1 + len, array[i]);
if(r < 0){
int insertPos = -(r + 1);
dp[insertPos] = array[i];
if(insertPos > len)
len++ ;
}
}
return len;
}

2.变种，如果是求最大子序列和？使用第一个思路很简单，只要让dp存和即可。

public int maxSumIS(int[] array){
int[] dp = new int[array.length];
dp[0] = array[0];
int max_sum = 0;
for(int i = 1; i < array.length; i++){
int max = array[i];
for(int j = 0; j < i; j++){
if(array[i] > array[j])
max = Math.max(dp[j] + array[i], dp[i]);
}
dp[i] = max;
max_sum = Math.max(max_sum, dp[i]);
}
return max_sum;
}