Задача: 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 {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        deque<int> queue;
        vector<int> dp(nums.size());
        int maxSum = INT_MIN;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (!queue.empty() && i - queue.front() > k) {
                queue.pop_front();
            }
            
            dp[i] = (queue.empty() ? 0 : dp[queue.front()]) + nums[i];
            
            while (!queue.empty() && dp[queue.back()] < dp[i]) {
                queue.pop_back();
            }
            
            if (dp[i] > 0) {
                queue.push_back(i);
            }
            
            maxSum = max(maxSum, dp[i]);
        }
        
        return maxSum;
    }
};

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