Задача: 689. Maximum Sum of 3 Non-Overlapping Subarrays
Сложность: hard

Дан целочисленный массив nums и целое число k. Найдите три непересекающихся подмассива длины k с максимальной суммой и верните их.

Верните результат в виде списка индексов, представляющих начальную позицию каждого интервала (нумерация с 0). Если существует несколько ответов, верните лексикографически наименьший.

Пример:

Input: nums = [1,2,1,2,6,7,5,1], k = 2
Output: [0,3,5]
Explanation: Subarrays [1, 2], [2, 6], [7, 5] correspond to the starting indices [0, 3, 5].
We could have also taken [2, 1], but an answer of [1, 3, 5] would be lexicographically larger.

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

1⃣Предположим, что фиксирован j. Нам нужно узнать на интервалах i∈[0,j−k] и l∈[j+k,len(W)−1], где наибольшее значение W[i] (и соответственно W[l]) встречается первым (то есть, с наименьшим индексом).

2⃣Мы можем решить эту задачу с помощью динамического программирования. Например, если мы знаем, что i - это место, где наибольшее значение W[i] встречается первым на [0,5], то на [0,6] первое появление наибольшего W[i] должно быть либо i, либо 6. Если, скажем, 6 лучше, тогда мы устанавливаем best = 6. В конце left[z] будет первым вхождением наибольшего значения W[i] на интервале i∈[0,z], а right[z] будет таким же, но на интервале i∈[z,len(W)−1].

3⃣Это означает, что для некоторого выбора j, кандидат на ответ должен быть (left[j - k], j, right[j + k]). Мы выбираем кандидата, который дает максимальное значение W[i] + W[j] + W[l].

😎 Решение:

class Solution {
    func maxSumOfThreeSubarrays(_ nums: [Int], _ k: Int) -> [Int] {
        var W = [Int](repeating: 0, count: nums.count - k + 1)
        var currSum = 0
        for i in 0..<nums.count {
            currSum += nums[i]
            if i >= k {
                currSum -= nums[i - k]
            }
            if i >= k - 1 {
                W[i - k + 1] = currSum
            }
        }

        var left = [Int](repeating: 0, count: W.count)
        var best = 0
        for i in 0..<W.count {
            if W[i] > W[best] {
                best = i
            }
            left[i] = best
        }

        var right = [Int](repeating: 0, count: W.count)
        best = W.count - 1
        for i in (0..<W.count).reversed() {
            if W[i] >= W[best] {
                best = i
            }
            right[i] = best
        }

        var ans = [-1, -1, -1]
        for j in k..<(W.count - k) {
            let i = left[j - k]
            let l = right[j + k]
            if ans[0] == -1 || W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]] {
                ans[0] = i
                ans[1] = j
                ans[2] = l
            }
        }
        return ans
    }
}

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