image.png
解法
动态规划，时间复杂度为O(N * N)
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
// 以i为结尾的字符串，最大升序列的值
int[] dp = new int[len];
// 初始化每个位置为1，最起码为1
Arrays.fill(dp, 1);
int maxRes = 1;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
// i 大于 j的情况下，在原有值上加1
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxRes = Math.max(maxRes, dp[i]);
}
return maxRes;
}
}
贪心算法+二分查找，O(NlogN)
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
// 代表递增序列长度为i时，最小的末尾字符串
int[] d = new int[len + 1];
int n = 1;
d[1] = nums[0];
for (int i = 1; i < len; i++) {
if (nums[i] > d[n]) {
d[++n] = nums[i];
} else {
// 寻找nums[i]在d数组中，大于d[pos],小于d[pos+1]的位置，去更新pos+1的位置为更小的值
// 下面的计算中，二分逼近，小于nums[i]的最大数，即pos位置
int l = 1;
int r = n;
int pos = 0;
while (l <= r) {
int mid = (l + r) / 2;
if (d[mid] < nums[i]) {
pos = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
d[pos + 1] = nums[i];
}
}
return n;
}
}
