问题描述
给定一个整数数组，要求找出其中最长单调递增的子序列的长度。题目链接：**点我**
样例输入输出
输入：[10,9,2,5,3,7,101,18]
输出：4
解释：最长单调递增子序列为：[2,3,7,101]
输入：[1,1]
输出：1
问题解法
解法一：动态规划
使用动态规划，用 dp[i] 表示以 nums[i] 结尾构成的子数组的最长单调递增子序列的长度，则动态转移方程为 dp[i] = if (nums[j] < nums[i]) max(dp[j] + 1), (0 < j < i)。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
int result = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] >= dp[i]) {
dp[i] = dp[j] + 1;
}
}
result = Math.max(result, dp[i] + 1);
}
return result;
}
}
|
解法二：贪心+二分法
此解法参考https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/。主要做法是：用 dp[i] 表示以 i + 1 个元素构成的单调递增数列的最后一个元素的最小值，遍历原数组，如果当前元素比 dp 数组最后一个元素大，则直接加到 dp 数组中，如果比它小，则在 dp 数组中找到第一个比它大的元素，然后将这个 dp 元素替换成当前 nums 数组的元素。由于 dp 数组是一个单调递增的数组，所以在上述的搜索过程中可以使用二分查找进行搜索。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int len = 1;
for (int i = 1; i < nums.length; i++) {
if (dp[len - 1] < nums[i]) {
dp[len] = nums[i];
len++;
continue;
}
int start = 0;
int end = len - 1;
int middle = 0;
while (start <= end) {
middle = (start + end) / 2;
if (dp[middle] == nums[i]) {
break;
}
if (dp[middle] < nums[i]) {
start = middle + 1;
} else {
end = middle - 1;
}
}
if (dp[middle] < nums[i]) {
dp[middle + 1] = nums[i];
} else {
dp[middle] = nums[i];
}
}
return len;
}
}
|
参考资料
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/