
Intuition
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.
Approach
- Define the DP Array:
- Use a 2D DP array
dp[i][j]
, wherei
is the index innums
andj
represents the number of changes allowed (from 0 tok
). -dp[i][j]
stores the length of the longest good subsequence that ends at indexi
with exactlyj
changes. - Initialize the DP Array:
- Set
dp[i][0]
to 1 for alli
because a single element subsequence is always a good subsequence with 0 changes. - Fill the DP Array:
- For each element
nums[i]
, check all previous elementsnums[p]
(wherep < i
). - Ifnums[p] == nums[i]
, extend the subsequence without adding a change. - Ifnums[p] != nums[i]
andj > 0
, extend the subsequence with one additional change. - Keep Track of the Maximum Length: - Continuously update the maximum length of the good subsequence found.
Approach Transition: From O(n^2*k) to O(n*k)
Problem Understanding
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.
Initial Solution: O(n^2*k)
Dynamic Programming Approach
Step 1: Initialize DP Table
- Create a 2D DP array
dp
of sizen x (k+1)
and initialize all values to0
. - Each
dp[i][j]
represents the length of the longest good subsequence ending at indexi
withj
changes.
Step 2: Base Case
- For each index
i
, if no changes are allowed (j == 0
), setdp[i][0] = 1
. - This initializes the longest subsequence length as
1
for each element in the array.
Step 3: Fill the DP Table
- For each index
i
from1
ton-1
: - For each value ofj
from0
tok
: - Initializedp[i][j] = 1
. - Iterate through all indicesp
from0
toi-1
: - Ifnums[p]
equalsnums[i]
, updatedp[i][j]
tomax(dp[i][j], dp[p][j] + 1)
. - Ifj > 0
, updatedp[i][j]
tomax(dp[i][j], dp[p][j - 1] + 1)
to allow for a change.
Complexity Analysis:
- Time Complexity: O(n^2*k)
- Space Complexity: O(n*k) for the DP table.
Optimized Solution: O(n*k)
Rolling Sum Optimization
Idea
- Utilize a rolling sum approach to optimize the inner loop, reducing the time complexity to O(n*k).
Step 1: Initialize DP Table and Variables
- Create a 2D DP array
dp
of sizen x (k+1)
and initialize all values to0
. - Initialize
res
to1
.
Step 2: Base Case
- For each index
i
, if no changes are allowed (j == 0
), setdp[i][0] = 1
.
Step 3: Fill the DP Table
- For each value of
j
from0
tok
: - Initializemax1 = 1
to track the maximum length of subsequence withj-1
changes up to the previous index. - Initialize amap
to track the last occurrence index of each number. - Iterate through each indexi
from1
ton-1
: - Updatedp[i][j]
based on the previous values and conditions as described in the initial solution. - Updateres
to the maximum length encountered. - Utilize themap
to efficiently find the last occurrence index of each number.
Complexity
- Time complexity: O(n \* k)
- We iterate through the array
nums
with two nested loops: one fork
and one for the lengthn
of the array. In each iteration, operations such as dictionary lookups and updates are done in constant time. - Space complexity: O(n \* k)
- The DP table requires O(n \* k) space to store the results for each index and number of changes. Additionally, the space for the dictionary is proportional to the number of unique elements in
nums
, which in the worst case is O(n).
Code
C++
class Solution {
public:
int maximumLength(std::vector& nums, int k) {
int n = nums.size();
if (n == 0) return 0;
std::vector> dp(n, std::vector(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 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;
}
};
Python
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
Java
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 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;
}
}
JavaScript
/**
* @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;
};
Go
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
}
C#
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 numMap = new Dictionary();
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;
}
}
Conclusion
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.