3176. 求出最长好子序列
题目链接https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-i/
题目描述
给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。
实例1:
输入：nums = [1,2,1,1,3], k = 2
输出：2
解释：最长的好子序列是 [1,2,1,1] 。
实例2:
输入：nums = [1,2,3,4,5,1], k = 0
输出：2
解释：最长好子序列为 [1,1] 。
题目解析
根据题目可知，我们需要找到一个整数序列，满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标 i 满足 seq[i] != seq[i + 1] 。
我们可以考虑使用动态规划来解决这个问题。
定义dp[i][j]表示以nums[i]结尾，最多有j个下标i 满足seq[i] != seq[i + 1]的子序列的长度。其中,0<=j<=k。
我们可以初始化dp[i][0]=1，表示以nums[i]结尾的，最多有0个下标i满足seq[i] != seq[i + 1]的子序列的长度为1。
那么，我们可以知道，当前dp[i][j]的值，和dp[cur][j]和dp[cur][j-1]有关。(0<=cur < i)
如果nums[cur]和nums[i]相同，那么dp[i][j]的值等于max(dp[i][j], dp[cur][j] + 1)。即，可以在nums[cur]为结尾的子序列加上nums[i]。
如果nums[cur]和nums[i]不同，那么dp[i][j]的值等于max(dp[i][j], dp[cur][j-1] + 1)。即，不可以在nums[cur]为结尾的子序列加上nums[i]。
最后，我们可以返回dp数组中最大值，即为最长的好子序列的长度。
代码实现
Go版本：
func maximumLength(nums []int, k int) int {n := len(nums)dp := make([][]int, n)for i := range dp {dp[i] = make([]int, k+1)}res := 0for i := 0; i < n; i++ {dp[i][0] = 1for j := 0; j <= k&&j<=i; j++ {for cur := 0; cur < i; cur++ {if nums[i] == nums[cur] {dp[i][j]=max(dp[i][j],dp[cur][j]+1)}else{if(j-1>=0){dp[i][j]=max(dp[i][j],dp[cur][j-1]+1)}}}res = max(res, dp[i][j])}}return res
}
Python版本：
class Solution(object):def maximumLength(self, nums, k):n = len(nums)dp = [[0] * (k + 1) for _ in range(n)]res = 0for i in range(n):dp[i][0] = 1for j in range(min(k, i) + 1):for cur in range(i):if nums[i] == nums[cur]:dp[i][j] = max(dp[i][j], dp[cur][j] + 1)else:if j - 1 >= 0:dp[i][j] = max(dp[i][j], dp[cur][j - 1] + 1)res = max(res, dp[i][j])return res
C++版本：
class Solution {
public:int maximumLength(vector<int>& nums, int k) {int n = nums.size();vector<vector<int>> dp(n, vector<int>(k + 1, 0));int res = 0;for (int i = 0; i < n; i++) {dp[i][0] = 1;for (int j = 0; j <= k && j <= i; j++) {for (int cur = 0; cur < i; cur++) {if (nums[i] == nums[cur]) {dp[i][j] = max(dp[i][j], dp[cur][j] + 1);} else {if (j - 1 >= 0) {dp[i][j] = max(dp[i][j], dp[cur][j - 1] + 1);}}}res = max(res, dp[i][j]);}}return res;}
};
