3176. 求出最长好子序列 I

https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-i/description/?envType=daily-question&envId=2024-09-06

题目描述

给你一个整数数组 nums 和一个 非负 整数 k 。如果一个整数序列 seq 满足在范围下标范围 [0, seq.length - 2] 中存在 不超过 k 个下标 i 满足 seq[i] != seq[i + 1] ，那么我们称这个整数序列为 好 序列。

请你返回 nums 中 好 

子序列

 的最长长度

示例 1：

输入：nums = [1,2,1,1], k = 2

输出：4

解释：

最长好子序列为 [1,2,1,1,3] 。

示例 2：

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

输出：2

解释：

最长好子序列为 [1,1] 。

提示：

• 1 <= nums.length <= 500
• 1 <= nums[i] <= 109
• 0 <= k <= min(nums.length, 25)

解题思路

循环去查看，如果nums[i]!=nums[i+1]则count+1

代码编写

public int maximumLength(int[] nums, int k) {
    if (nums.length == 0) {
        return 0;
    } else if (nums.length == 1) {
        return 1;
    }
    int seqLen = 0;
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        int tempSeqLen = 0;
        int index = i;
        while (true) {
            if (count > k) {
                break;
            }
            int next = index + 1;
            if (index == nums.length - 1) {
                next = 0;
            }
            if (nums[index] != nums[next]) {
                count++;
            }
            index++;
            tempSeqLen++;
            index=index%nums.length;
            if (index == i) {
                return tempSeqLen;
            }
        }
        seqLen = Math.max(tempSeqLen, seqLen);
    }
    return seqLen;
}

单元测试

System.out.println(new S3176().maximumLength(new int[]{1, 2, 1, 1, 3}, 2));// 4  
System.out.println(new S3176().maximumLength(new int[]{13,9,13}, 1));// 2

额外补充

解答理解错误了，seq[i]!=seq[i+1] 不是nums[i]!=nums[i+1]