三个无重叠子数组的最大和。给定数组 nums 由正整数组成,找到三个互不重叠的子数组的最大和。每个子数组的长度为k,我们要使这3*k个项的和最大化。返回每个区间起始索引的列表(索引从 0 开始)。如果有多个结果,返回字典序最小的一个。
时间紧,见代码。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
nums := []int{1, 2, 1, 2, 6, 7, 5, 1}
k := 2
ret := maxSumOfThreeSubarrays(nums, k)
fmt.Println(ret)
}
func maxSumOfThreeSubarrays(nums []int, k int) []int {
N := len(nums)
range2 := make([]int, N)
left := make([]int, N)
sum := 0
for i := 0; i < k; i++ {
sum += nums[i]
}
range2[0] = sum
left[k-1] = 0
max := sum
for i := k; i < N; i++ {
sum = sum - nums[i-k] + nums[i]
range2[i-k+1] = sum
left[i] = left[i-1]
if sum > max {
max = sum
left[i] = i - k + 1
}
}
sum = 0
for i := N - 1; i >= N-k; i-- {
sum += nums[i]
}
max = sum
right := make([]int, N)
right[N-k] = N - k
for i := N - k - 1; i >= 0; i-- {
sum = sum - nums[i+k] + nums[i]
right[i] = right[i+1]
if sum >= max {
max = sum
right[i] = i
}
}
a := 0
b := 0
c := 0
max = 0
for i := k; i < N-2*k+1; i++ { // 中间一块的起始点 (0...k-1)选不了 i == N-1
part1 := range2[left[i-1]]
part2 := range2[i]
part3 := range2[right[i+k]]
if part1+part2+part3 > max {
max = part1 + part2 + part3
a = left[i-1]
b = i
c = right[i+k]
}
}
return []int{a, b, c}
}
执行结果如下: