Задача: 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 {
    func constrainedSubsetSum(_ nums: [Int], _ k: Int) -> Int {
        var queue = [Int]()
        var dp = [Int](repeating: 0, count: nums.count)
        var maxSum = Int.min
        
        for i in 0..<nums.count {
            if !queue.isEmpty && i - queue.first! > k {
                queue.removeFirst()
            }
            
            dp[i] = (!queue.isEmpty ? dp[queue.first!] : 0) + nums[i]
            
            while !queue.isEmpty && dp[queue.last!] < dp[i] {
                queue.removeLast()
            }
            
            if dp[i] > 0 {
                queue.append(i)
            }
            
            maxSum = max(maxSum, dp[i])
        }
        
        return maxSum
    }
}

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