FastPrep
Problem · Dynamic Programming

Find the Maximum Length of a Good Subsequence I (LC 3176 :)

Learn this problem
● MediumSnowflake logoSnowflakeINTERNOA
See Snowflake hiring insights

Problem statement

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].

Return the maximum possible length of a good subsequence of nums.

Function

maxLengthGoodSubsequence(nums: int[], k: int) → int

Complete the function maxLengthGoodSubsequence in the editor.

maxLengthGoodSubsequence has the following parameters:

  1. 1. int[] nums: an array of integers
  2. 2. int k: a non-negative integer

Returns

int: the maximum possible length of a good subsequence

🌷 All credits go to the incredible Lie ༊·° 𓇢𓆸

Examples

Example 1

nums = [1,2,1,1,3]k = 2return = 4

The maximum length subsequence is [1,2,1,1,3].

Example 2

nums = [1,2,3,4,5,1]k = 0return = 2
The maximum length subsequence is [1,2,3,4,5,1].

Constraints

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

More Snowflake problems

drafts saved locally
public int maxLengthGoodSubsequence(int[] nums, int k) {
  // write your code here
}
nums[1,2,1,1,3]
k2
expected4
checking account