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就是其所在的子序列的长度。