300. Longest Increasing Subsequence

题目链接：https://leetcode.cn/problems/longest-increasing-subsequence/

方法一动态规划

1 方法思想

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度，注意：必须是以num[i]结尾的上升子序列。
dp[i]中存放的是以所有以num[i]结尾的可构成最长子序列长度的最大值。
最后求最大值时，需要对dp数组进行遍历取所有可能的最大值。

2 代码实现

class Solution {
	public int lengthOfLIS(int[] nums) {
			if (nums == null) return 0;
		int len = nums.length;
		int[] dp = new int[len];
		int result = 1;
		for (int i = 0; i < len; i++) {
			dp[i] = 1;
		}
		for (int i = 1; i < len; i++) {
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			if(dp[i] > result) result = dp[i];
		}

		return result;
	}
}

3 复杂度分析

时间复杂度：O(n^2)
空间复杂度：O(n)

4 涉及到知识点

这里的不同时，以每个num[i]结尾时的影响dp的状态。

方法二二分法 + 贪婪算法

1 方法思想

dp[len]中保存的是最长序列长度为len时的末尾元素的最小值。dp是单调递增的。
其中len就是最后所求的最长序列长度，并且可以使用二分法更新dp中的元素，使其保证dp[len]其中的元素都是长度为len时的最小元素。

最后整个算法流程为：
设当前已求出的最长上升子序列的长度len（初始时为 1），从前往后遍历数组 nums，在遍历到 nums[i]时：

如果 nums[i]>dp[len] ，则直接加入到 dp数组末尾，并更新len = len +1;
否则，在 dp数组中二分查找，找到第一个比nums[i]小的数 d[k] ，并更新 d[k + 1] =nums[i]。

在这里插入代码片

2 代码实现

class Solution {
	public int lengthOfLIS(int[] nums) {
		if (nums == null) return 0;
		int len = 1;
		int[] dp = new int[nums.length + 1];
		dp[1] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			if (nums[i] > dp[len]) {
				len++;
				dp[len] = nums[i];
			} else {
				int l = 1;
				int r = len;
				int pos = 0;
				while (l <= r) {
					int mid = l + (r - l) / 2;
					if (dp[mid] < nums[i]) {
						pos = mid;
						l = mid + 1;
					} else {
						r = mid - 1;
					}
				}
				dp[pos + 1] = nums[i];
			}
			
		}
		
		return len;
	}
}

3 复杂度分析

时间复杂度：O(n*log^n)
空间复杂度：O(n)

收获和总结

1.遇到的困难？

如何理解dp数组的状态更新，采用二分查找的目的就是可以保证dp[len]中的元素是遍历到num[i]时，从0到i中的最小元素（二分法中是找的第一个大于dp[k]的位置，并将num[i]插入）。

2 收获

学习链接

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF
https://leetcode.cn/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-by-leetcode-soluti/