Dare2Solve
To find the longest good subsequence where there are at most k
changes allowed (i.e., adjacent elements that are different), we can use dynamic programming. The idea is to maintain a DP table that tracks the length of the longest good subsequence ending at each index with a certain number of changes. By iterating through the array and updating this table based on the conditions specified, we can find the maximum length of such a subsequence.
Define the DP Array:
dp[i][j]
, where i
is the index in nums
and j
represents the number of changes allowed (from 0 to k
).dp[i][j]
stores the length of the longest good subsequence that ends at index i
with exactly j
changes.Initialize the DP Array:
dp[i][0]
to 1 for all i
because a single element subsequence is always a good subsequence with 0 changes.Fill the DP Array:
nums[i]
, check all previous elements nums[p]
(where p < i
).nums[p] == nums[i]
, extend the subsequence without adding a change.nums[p] != nums[i]
and j > 0
, extend the subsequence with one additional change.Keep Track of the Maximum Length:
Given an integer array nums
and a non-negative integer k
, find the maximum possible length of a good subsequence, where a good subsequence allows at most k
adjacent indices with unequal elements.
dp
of size n x (k+1)
and initialize all values to 0
.dp[i][j]
represents the length of the longest good subsequence ending at index i
with j
changes.i
, if no changes are allowed (j == 0
), set dp[i][0] = 1
.1
for each element in the array.i
from 1
to n-1
:
j
from 0
to k
:
dp[i][j] = 1
.p
from 0
to i-1
:
nums[p]
equals nums[i]
, update dp[i][j]
to max(dp[i][j], dp[p][j] + 1)
.j > 0
, update dp[i][j]
to max(dp[i][j], dp[p][j - 1] + 1)
to allow for a change.dp
of size n x (k+1)
and initialize all values to 0
.res
to 1
.i
, if no changes are allowed (j == 0
), set dp[i][0] = 1
.j
from 0
to k
:
max1 = 1
to track the maximum length of subsequence with j-1
changes up to the previous index.map
to track the last occurrence index of each number.i
from 1
to n-1
:
dp[i][j]
based on the previous values and conditions as described in the initial solution.res
to the maximum length encountered.map
to efficiently find the last occurrence index of each number.nums
with two nested loops: one for k
and one for the length n
of the array. In each iteration, operations such as dictionary lookups and updates are done in constant time.nums
, which in the worst case is O(n).class Solution {
public:
int maximumLength(std::vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) return 0;
std::vector<std::vector<int>> dp(n, std::vector<int>(k + 1, 0));
for (int i = 0; i < n; ++i) dp[i][0] = 1;
int res = 1;
for (int j = 0; j <= k; ++j) {
int max1 = 1;
std::unordered_map<int, int> numMap;
numMap[nums[0]] = 0;
for (int i = 1; i < n; ++i) {
dp[i][j] = 1;
if (i > 0 && j > 0) max1 = std::max(max1, dp[i - 1][j - 1] + 1);
dp[i][j] = std::max(dp[i][j], max1);
if (numMap.find(nums[i]) != numMap.end()) {
dp[i][j] = std::max(dp[i][j], dp[numMap[nums[i]]][j] + 1);
}
numMap[nums[i]] = i;
res = std::max(res, dp[i][j]);
}
}
return res;
}
};
class Solution:
def maximumLength(self, nums: List[int], k: int) -> int:
n = len(nums)
if n == 0:
return 0
dp = [[0] * (k + 1) for _ in range(n)]
for i in range(n):
dp[i][0] = 1
res = 1
for j in range(k + 1):
max1 = 1
num_map = {nums[0]: 0}
for i in range(1, n):
dp[i][j] = 1
if i > 0 and j > 0:
max1 = max(max1, dp[i - 1][j - 1] + 1)
dp[i][j] = max(dp[i][j], max1)
if nums[i] in num_map:
dp[i][j] = max(dp[i][j], dp[num_map[nums[i]]][j] + 1)
num_map[nums[i]] = i
res = max(res, dp[i][j])
return res
class Solution {
public int maximumLength(int[] nums, int k) {
int n = nums.length;
if (n == 0) return 0;
int[][] dp = new int[n][k + 1];
for (int i = 0; i < n; ++i) dp[i][0] = 1;
int res = 1;
for (int j = 0; j <= k; ++j) {
int max1 = 1;
Map<Integer, Integer> numMap = new HashMap<>();
numMap.put(nums[0], 0);
for (int i = 1; i < n; ++i) {
dp[i][j] = 1;
if (i > 0 && j > 0) max1 = Math.max(max1, dp[i - 1][j - 1] + 1);
dp[i][j] = Math.max(dp[i][j], max1);
if (numMap.containsKey(nums[i])) {
dp[i][j] = Math.max(dp[i][j], dp[numMap.get(nums[i])][j] + 1);
}
numMap.put(nums[i], i);
res = Math.max(res, dp[i][j]);
}
}
return res;
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var maximumLength = function (nums, k) {
const n = nums.length;
if (n === 0) return 0;
const dp = Array.from({ length: n }, () => Array(k + 1).fill(0));
for (let i = 0; i < n; ++i) dp[i][0] = 1;
let res = 1;
for (let j = 0; j <= k; ++j) {
var max1 = 1;
var map = new Map();
map.set(nums[0], 0);
for (let i = 1; i < n; ++i) {
dp[i][j] = 1;
if (i > 0 && j > 0) max1 = Math.max(max1, dp[i - 1][j - 1] + 1);
dp[i][j] = Math.max(dp[i][j], max1);
if (map.has(nums[i])) {
dp[i][j] = Math.max(dp[i][j], dp[map.get(nums[i])][j] + 1);
}
map.set(nums[i], i);
res = Math.max(res, dp[i][j]);
}
}
return res;
};
func maximumLength(nums []int, k int) int {
n := len(nums)
if n == 0 {
return 0
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, k+1)
}
for i := 0; i < n; i++ {
dp[i][0] = 1
}
res := 1
for j := 0; j <= k; j++ {
max1 := 1
numMap := make(map[int]int)
numMap[nums[0]] = 0
for i := 1; i < n; i++ {
dp[i][j] = 1
if i > 0 && j > 0 {
max1 = max(max1, dp[i-1][j-1]+1)
}
dp[i][j] = max(dp[i][j], max1)
if idx, exists := numMap[nums[i]]; exists {
dp[i][j] = max(dp[i][j], dp[idx][j]+1)
}
numMap[nums[i]] = i
res = max(res, dp[i][j])
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
public class Solution {
public int MaximumLength(int[] nums, int k) {
int n = nums.Length;
if (n == 0) return 0;
int[][] dp = new int[n][];
for (int i = 0; i < n; ++i) {
dp[i] = new int[k + 1];
}
for (int i = 0; i < n; ++i) dp[i][0] = 1;
int res = 1;
for (int j = 0; j <= k; ++j) {
int max1 = 1;
Dictionary<int, int> numMap = new Dictionary<int, int>();
numMap[nums[0]] = 0;
for (int i = 1; i < n; ++i) {
dp[i][j] = 1;
if (i > 0 && j > 0) max1 = Math.Max(max1, dp[i - 1][j - 1] + 1);
dp[i][j] = Math.Max(dp[i][j], max1);
if (numMap.ContainsKey(nums[i])) {
dp[i][j] = Math.Max(dp[i][j], dp[numMap[nums[i]]][j] + 1);
}
numMap[nums[i]] = i;
res = Math.Max(res, dp[i][j]);
}
}
return res;
}
}
By utilizing dynamic programming, we effectively track the longest good subsequence ending at each index with a certain number of allowed changes. This method ensures that we consider all possible subsequences and changes efficiently. The algorithm operates within acceptable time and space complexities, making it suitable for large input sizes typical in competitive programming and coding interviews.