689. Maximum Sum of 3 Non-Overlapping Subarrays
leetcode hard
Task
Дан целочисленный массив 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.
C# solution
matched/originalpublic class Solution {
public int[] MaxSumOfThreeSubarrays(int[] nums, int k) {
int[] W = new int[nums.Length - k + 1];
int currSum = 0;
for (int i = 0; i < nums.Length; i++) {
currSum += nums[i];
if (i >= k) {
currSum -= nums[i - k];
}
if (i >= k - 1) {
W[i - k + 1] = currSum;
}
}
int[] left = new int[W.Length];
int best = 0;
for (int i = 0; i < W.Length; i++) {
if (W[i] > W[best]) best = i;
left[i] = best;
}
int[] right = new int[W.Length];
best = W.Length - 1;
for (int i = W.Length - 1; i >= 0; i--) {
if (W[i] >= W[best]) best = i;
right[i] = best;
}
int[] ans = new int[] {-1, -1, -1};
for (int j = k; j < W.Length - k; j++) {
int i = left[j - k], 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;
}
}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 vector<int>& MaxSumOfThreeSubarrays(vector<int>& nums, int k) {
vector<int>& W = new int[nums.size() - k + 1];
int currSum = 0;
for (int i = 0; i < nums.size(); i++) {
currSum += nums[i];
if (i >= k) {
currSum -= nums[i - k];
}
if (i >= k - 1) {
W[i - k + 1] = currSum;
}
}
vector<int>& left = new int[W.size()];
int best = 0;
for (int i = 0; i < W.size(); i++) {
if (W[i] > W[best]) best = i;
left[i] = best;
}
vector<int>& right = new int[W.size()];
best = W.size() - 1;
for (int i = W.size() - 1; i >= 0; i--) {
if (W[i] >= W[best]) best = i;
right[i] = best;
}
vector<int>& ans = new int[] {-1, -1, -1};
for (int j = k; j < W.size() - k; j++) {
int i = left[j - k], 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;
}
}Java solution
matched/originalclass Solution {
public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
int[] W = new int[nums.length - k + 1];
int currSum = 0;
for (int i = 0; i < nums.length; i++) {
currSum += nums[i];
if (i >= k) {
currSum -= nums[i - k];
}
if (i >= k - 1) {
W[i - k + 1] = currSum;
}
}
int[] left = new int[W.length];
int best = 0;
for (int i = 0; i < W.length; i++) {
if (W[i] > W[best]) best = i;
left[i] = best;
}
int[] right = new int[W.length];
best = W.length - 1;
for (int i = W.length - 1; i >= 0; i--) {
if (W[i] >= W[best]) {
best = i;
}
right[i] = best;
}
int[] ans = new int[]{-1, -1, -1};
for (int j = k; j < W.length - k; j++) {
int i = left[j - k], 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;
}
}JavaScript solution
matched/originalclass Solution {
maxSumOfThreeSubarrays(nums, k) {
const W = new Array(nums.length - k + 1).fill(0);
let currSum = 0;
for (let i = 0; i < nums.length; i++) {
currSum += nums[i];
if (i >= k) {
currSum -= nums[i - k];
}
if (i >= k - 1) {
W[i - k + 1] = currSum;
}
}
const left = new Array(W.length).fill(0);
let best = 0;
for (let i = 0; i < W.length; i++) {
if (W[i] > W[best]) best = i;
left[i] = best;
}
const right = new Array(W.length).fill(0);
best = W.length - 1;
for (let i = W.length - 1; i >= 0; i--) {
if (W[i] >= W[best]) best = i;
right[i] = best;
}
const ans = [-1, -1, -1];
for (let j = k; j < W.length - k; j++) {
const i = left[j - k];
const 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;
}
}Python solution
matched/originalclass Solution:
def maxSumOfThreeSubarrays(self, nums, k):
W = [0] * (len(nums) - k + 1)
currSum = 0
for i in range(len(nums)):
currSum += nums[i]
if i >= k:
currSum -= nums[i - k]
if i >= k - 1:
W[i - k + 1] = currSum
left = [0] * len(W)
best = 0
for i in range(len(W)):
if W[i] > W[best]:
best = i
left[i] = best
right = [0] * len(W)
best = len(W) - 1
for i in range(len(W) - 1, -1, -1):
if W[i] >= W[best]:
best = i
right[i] = best
ans = [-1, -1, -1]
for j in range(k, len(W) - k):
i, l = left[j - k], right[j + k]
if ans[0] == -1 or W[i] + W[j] + W[l] > W[ans[0]] + W[ans[1]] + W[ans[2]]:
ans = [i, j, l]
return ansGo solution
matched/originalpackage main
func maxSumOfThreeSubarrays(nums []int, k int) []int {
W := make([]int, len(nums)-k+1)
currSum := 0
for i := 0; i < len(nums); i++ {
currSum += nums[i]
if i >= k {
currSum -= nums[i-k]
}
if i >= k-1 {
W[i-k+1] = currSum
}
}
left := make([]int, len(W))
best := 0
for i := 0; i < len(W); i++ {
if W[i] > W[best] {
best = i
}
left[i] = best
}
right := make([]int, len(W))
best = len(W) - 1
for i := len(W) - 1; i >= 0; i-- {
if W[i] >= W[best] {
best = i
}
right[i] = best
}
ans := []int{-1, -1, -1}
for j := k; j < len(W)-k; j++ {
i, l := left[j-k], right[j+k]
if ans[0] == -1 || W[i]+W[j]+W[l] > W[ans[0]]+W[ans[1]]+W[ans[2]] {
ans[0], ans[1], ans[2] = i, j, l
}
}
return ans
}Explanation
Algorithm
Предположим, что фиксирован j. Нам нужно узнать на интервалах i∈[0,j−k] и l∈[j+k,len(W)−1], где наибольшее значение W[i] (и соответственно W[l]) встречается первым (то есть, с наименьшим индексом).
Мы можем решить эту задачу с помощью динамического программирования. Например, если мы знаем, что 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].
Это означает, что для некоторого выбора j, кандидат на ответ должен быть (left[j - k], j, right[j + k]). Мы выбираем кандидата, который дает максимальное значение W[i] + W[j] + W[l].
😎