22.10.2023
1425. Constrained Subsequence Sum hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/377
Problem TLDR
Max sum of subsequence i - j <= k
Intuition
The naive DP approach is to do DFS and memoization:
fun constrainedSubsetSum(nums: IntArray, k: Int): Int {
val dp = mutableMapOf<Int, Int>()
fun dfs(i: Int): Int = if (i >= nums.size) 0 else dp.getOrPut(i) {
var max = nums[i]
for (j in 1..k) max = max(max, nums[i] + dfs(i + j))
max
}
return (0..<nums.size).maxOf { dfs(it) }
}
This solution takes O(nk) time and gives TLE.
Let’s rewrite it to the iterative version to think about further optimization:
fun constrainedSubsetSum(nums: IntArray, k: Int): Int {
val dp = mutableMapOf<Int, Int>()
for (i in nums.indices)
dp[i] = nums[i] + (i - k..i).maxOf { dp[it] ?: 0 }
return dp.values.max()
}
Next, read a hint :) It will suggest using a Heap. Indeed, looking at this code, we’re just choosing a maximum value from the last k
values:
fun constrainedSubsetSum(nums: IntArray, k: Int): Int =
with (PriorityQueue<Int>(reverseOrder())) {
val dp = mutableMapOf<Int, Int>()
for (i in nums.indices) {
if (i - k > 0) remove(dp[i - k - 1])
dp[i] = nums[i] + max(0, peek() ?: 0)
add(dp[i])
}
dp.values.max()
}
This solution takes O(nlog(k)) time and still gives TLE.
Let’s look at other’s people solutions, just take a hint: decreasing queue
. This technique must be remembered, as it is a common trick to find a maximum in a sliding window with O(1) time.
Approach
Decreasing queue
flushes all the values that smaller than the current.
we’ll store the indices to remove them later if out of
k
careful with indices
Complexity
Time complexity:
O(n)Space complexity:
O(k)
Code
fun constrainedSubsetSum(nums: IntArray, k: Int): Int =
with (ArrayDeque<Int>()) {
for (i in nums.indices) {
if (isNotEmpty() && first() < i - k) removeFirst()
if (isNotEmpty()) nums[i] += max(0, nums[first()])
while (isNotEmpty() && nums[last()] < nums[i]) removeLast()
addLast(i)
}
nums.max()
}