今日任务：

1. LeetCode300 最长递增子序列
2. LeetCode674 最长连续递增子序列
3. LeetCode718 最长重复子数组

资料来源：

1. 代码随想录 | LeetCode300 最长递增子序列
2. 代码随想录 | LeetCode674 最长连续递增子序列
3. 代码随想录 | LeetCode718 最长重复子数组

1 LeetCode300 最长递增子序列

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

输入：nums = [0,1,0,3,2,3]
输出：4

输入：nums = [7,7,7,7,7,7,7]
输出：1

这题还是，循环尝试选取每个元素。对于每个元素来说，要么就是比之前的元素要大，要选上；要么就是不比之前的元素大，重新开始选这两种状态，递推公式这就有了。

go
func lengthOfLIS(nums []int) int {
	dpArray := make([]int, len(nums))
	for i := range dpArray { // 初始化 因为每个数字自己就是一个递增子序列
		dpArray[i] = 1
	}
	maxValue := 1
	for i := 1; i < len(nums); i++ {
		for j := i - 1; j >= 0; j-- { // 这题不要求连续 所以要把之前选过的元素都循环一次看看连得上连不上
			if nums[j] < nums[i] {
				dpArray[i] = max(dpArray[i], dpArray[j] + 1) // 递推公式
			}
		}
		if dpArray[i] > maxValue {
			maxValue = dpArray[i]
		}
	}
	return maxValue
}

2 LeetCode674 最长连续递增子序列

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

这题和上一个题差不多，甚至还更简单一点。上一题由于子序列可以不连续，所以需要两层循环，内层循环查之前的元素能否连上。这次一层循环就够用了，只查nums[i - 1]就行了。

go
func findLengthOfLCIS(nums []int) int {
	dpArray := make([]int, len(nums))
	for i := range dpArray {
		dpArray[i] = 1
	}
	result := 1
	for i := 1; i < len(nums); i++ {
		if nums[i] > nums[i - 1] {
			dpArray[i] = dpArray[i - 1] + 1
		}
		if dpArray[i] > result {
			result = dpArray[i]
		}
	}
	return result
}

3 LeetCode718 最长重复子数组

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。

输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

这题需要用二维数组，两个维度分别对应两个数组，这样才能所有元素都匹配一次。对于dpArray[j][i]来说，如果nums1[i] == nums2[j]成立，说明找到了一个相同元素，从dpArray[j - 1][i - 1]进行状态推导（因为是连续的，如果要选上这个元素，两个数组得一起选）。

另外，参照01背包问题，这题可以状态压缩为一维数组。

go
func findLength(nums1 []int, nums2 []int) int {
	dpArray := make([][]int, len(nums2))
	for i := range dpArray {
		dpArray[i] = make([]int, len(nums1))
	}
	result := 0
        // 初始化 这个初始化方法也和01背包有点像的
	for i := 0; i < len(nums1); i++ {
		if nums1[i] == nums2[0] {
			dpArray[0][i] = 1
			result = 1
		}
	}
	for i := 0; i < len(nums2); i++ {
		if nums1[0] == nums2[i] {
			dpArray[i][0] = 1
			result = 1
		}
	}
        // 开始推导
	for i := 1; i < len(nums1); i++ {
		for j := 1; j < len(nums2); j++ {
			if nums1[i] == nums2[j] {
				dpArray[j][i] = dpArray[j - 1][i - 1] + 1
				if dpArray[j][i] > result {
					result = dpArray[j][i]
				}
			}
		}
	}
	return result
}