Задача: 1425. Constrained Subsequence Sum
Сложность: hard

Дан целочисленный массив 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].

👨‍💻 Алгоритм:

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

2⃣Итерируйте 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.

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

😎 Решение:

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;
    }
}

Ставь 👍 и забирай 📚 Базу знаний