1425. Constrained Subsequence Sum

leetcode hard

#array#csharp#dynamic-programming#hard#leetcode#math#queue

Task

Дан целочисленный массив nums и целое число k, верните максимальную сумму непустой подпоследовательности этого массива, такую, что для любых двух последовательных целых чисел в подпоследовательности nums[i] и nums[j], где i < j, выполняется условие j - i <= k.

Подпоследовательность массива получается путем удаления некоторого количества элементов (может быть ноль) из массива, оставляя оставшиеся элементы в их исходном порядке.

Пример:

Input: nums = [10,2,-10,5,20], k = 2

Output: 37

Explanation: The subsequence is [10, 2, 5, 20].

C# solution

matched/original

public class Solution {
    public int ConstrainedSubsetSum(int[] nums, int k) {
        Deque<int> queue = new LinkedList<int>();
        int[] dp = new int[nums.Length];
        int maxSum = int.MinValue;
        
        for (int i = 0; i < nums.Length; i++) {
            if (queue.Count > 0 && i - queue.First.Value > k) {
                queue.RemoveFirst();
            }
            
            dp[i] = (queue.Count > 0 ? dp[queue.First.Value] : 0) + nums[i];
            
            while (queue.Count > 0 && dp[queue.Last.Value] < dp[i]) {
                queue.RemoveLast();
            }
            
            if (dp[i] > 0) {
                queue.AddLast(i);
            }
            
            maxSum = Math.Max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ConstrainedSubsetSum(vector<int>& nums, int k) {
        Deque<int> queue = new LinkedList<int>();
        vector<int>& dp = new int[nums.size()];
        int maxSum = int.MinValue;
        
        for (int i = 0; i < nums.size(); i++) {
            if (queue.size() > 0 && i - queue.First.Value > k) {
                queue.RemoveFirst();
            }
            
            dp[i] = (queue.size() > 0 ? dp[queue.First.Value] : 0) + nums[i];
            
            while (queue.size() > 0 && dp[queue.Last.Value] < dp[i]) {
                queue.RemoveLast();
            }
            
            if (dp[i] > 0) {
                queue.AddLast(i);
            }
            
            maxSum = max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

Java solution

matched/original

class Solution {
    public int constrainedSubsetSum(int[] nums, int k) {
        Deque<Integer> queue = new ArrayDeque<>();
        int dp[] = new int[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            if (!queue.isEmpty() && i - queue.peek() > k) {
                queue.poll();
            }
            
            dp[i] = (!queue.isEmpty() ? dp[queue.peek()] : 0) + nums[i];
            while (!queue.isEmpty() && dp[queue.peekLast()] < dp[i]) {
                queue.pollLast();
            }
            
            if (dp[i] > 0) {
                queue.offer(i);
            }
        }
        
        int ans = Integer.MIN_VALUE;
        for (int num : dp) {
            ans = Math.max(ans, num);
        }
        
        return ans;
    }
}

JavaScript solution

matched/original

class Solution {
    constrainedSubsetSum(nums, k) {
        const queue = [];
        const dp = new Array(nums.length).fill(0);
        let maxSum = Number.MIN_SAFE_INTEGER;
        
        for (let i = 0; i < nums.length; i++) {
            if (queue.length > 0 && i - queue[0] > k) {
                queue.shift();
            }
            
            dp[i] = (queue.length > 0 ? dp[queue[0]] : 0) + nums[i];
            
            while (queue.length > 0 && dp[queue[queue.length - 1]] < dp[i]) {
                queue.pop();
            }
            
            if (dp[i] > 0) {
                queue.push(i);
            }
            
            maxSum = Math.max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
}

Go solution

matched/original

func constrainedSubsetSum(nums []int, k int) int {
    queue := []int{}
    dp := make([]int, len(nums))
    maxSum := nums[0]
    
    for i := 0; i < len(nums); i++ {
        if len(queue) > 0 && i - queue[0] > k {
            queue = queue[1:]
        }
        
        if len(queue) > 0 {
            dp[i] = dp[queue[0]] + nums[i]
        } else {
            dp[i] = nums[i]
        }
        
        for len(queue) > 0 && dp[queue[len(queue) - 1]] < dp[i] {
            queue = queue[:len(queue) - 1]
        }
        
        if dp[i] > 0 {
            queue = append(queue, i)
        }
        
        if dp[i] > maxSum {
            maxSum = dp[i]
        }
    }
    
    return maxSum
}

Explanation

Algorithm

Инициализируйте очередь queue и массив dp той же длины, что и nums.

Итерируйте i по индексам nums:

Если i минус первый элемент queue больше k, удалите элемент из начала queue.

Установите dp[i] как dp[queue.front()] + nums[i]. Если queue пуст, используйте 0 вместо dp[queue.front()].

Пока dp[queue.back()] меньше dp[i], удаляйте элементы с конца queue.

Если dp[i] > 0, добавьте i в конец queue.

Верните максимальное значение в массиве dp.

😎