代码随想录day43 || 300 最长递增子序列，674 最长连续递增子序列，718 最长重复子数组

300 最长递增子序列

var path []int
var res int
func lengthOfLIS(nums []int) int {
	// 尝试回溯思路
	if len(nums) == 1 {
		return 1
	}

	path = []int{}
	res = 0
	backtracking(nums)
	return res
}

func backtracking(nums []int) {
	if len(nums) == 0 {
		if len(path) > res {
			res = len(path)
		}
		//fmt.Println(path, res )
		return
	}

	for i:=0; i<len(nums); i++ {
		if len(path)==0 || len(path)>0 && nums[i] > path[len(path) - 1]{
			path = append(path, nums[i])
			backtracking(nums[i+1: ])
			path = path[0 : len(path) - 1]
		}else {
			backtracking(nums[i+1: ])
		}
	}

}

func lengthOfLIS(nums []int) int {
	// 动态规划
	// dp[i] 表示以nums[i] 为结尾的最长递增子序列的长度
	// 递推 dp[i] = max(dp[j] + 1, dp[i]) j: 0-> i-1; if nums[i] > nums[j]
	// dp[0] = 0, dp[1] = 1
	// 遍历数组
	// print

	if len(nums) == 1{
		return 1
	}

	var dp = make([]int, len(nums))
	for idx, _ := range dp{
		dp[idx] = 1
	}
	for i:=1; i<len(nums); i++ {
		for j:=0; j<i; j++{
			if nums[i] > nums[j] {
				dp[i] = max(dp[i], dp[j] + 1)
			}
		}
	}
	//fmt.Println(dp)
	return maxslice(dp)
}

func maxslice (dp []int) int {
	var m int
	for _, v := range dp{
		if v > m {
			m = v
		}
	}
	return m
}

674 最长递增子序列

func findLengthOfLCIS(nums []int) int {
	// 相比300 最长递增子序列条件多了一个连续，所以，递推公式也要判断连续情况
	// dp[i] 表示以nums[i] 结尾的最长连续子序列长度
	// if nums[i] > nums[i-1] {dp[i] = dp[i-1]+1}
	// dp数组初始化为1
	// print

	if len(nums) == 1{
		return 1
	}
	var dp = make([]int, len(nums))
	for idx, _ := range dp {
		dp[idx] = 1
	}

	for i:=1; i<len(nums); i++ {
		if nums[i]> nums[i-1]{
			dp[i] = dp[i-1]+1
		}
	}
	//fmt.Println(dp)
	return maxslice(dp)
}

718 最长重复子数组

func findLength(nums1 []int, nums2 []int) int {
	// 本题考虑二维数组
	// dp[i][j] 表示对应nums1[i], nums2[j] 的最长公共子数组长度
	// dp[i][j] = dp[i-1][j-1] + 1 (if nums[i] == nums[j]) else { dp[i][j] = dp[i-1][j-1] }
	// 初始化为0
	// 两个数组遍历顺序无所谓
	// 打印
	var dp = make([][]int, len(nums1) + 1)
	for idx, _ := range dp {
		dp[idx] = make([]int, len(nums2) + 1)
	}
	var max int = 0
	for i:=0; i<len(nums1); i++{
		for j:=0; j<len(nums2); j++{
			if nums1[i] == nums2[j] {
				dp[i+1][j+1] = dp[i][j] + 1
			}

			if dp[i+1][j+1] > max{
				max = dp[i+1][j+1]
			}
		}
	}

	//fmt.Println(dp)
	return max
}

// 一个坑点在于需要连续但是题目没有明确说明
[0,1,1,1,1] [1,0,1,0,1]  正确答案是【0，1】= 3  而不是【1，1，1】= 3