福大大 答案2021-04-25：
前缀和 左大右小的双端队列。时间太晚了，所以写得简单。
代码用golang编写。代码如下：
代码语言：txt复制package main
import (
"container/list"
"fmt"
)
func main() {
arr := []int{1, 2, -3, 4, -5}
ret := maxSum(arr, 5)
fmt.Println(ret)
}
// O(N)的解法，最优解
func maxSum(arr []int, M int) int {
if len(arr) == 0 || M < 1 {
return 0
}
N := len(arr)
//前缀和
sum := make([]int, N)
sum[0] = arr[0]
for i := 1; i < N; i {
sum[i] = sum[i-1] arr[i]
}
//双端队列
qmax := list.New()
i := 0
end := getMin(N, M)
for ; i < end; i {
for qmax.Len() > 0 && sum[qmax.Back().Value.(int)] <= sum[i] {
qmax.Remove(qmax.Back())
}
qmax.PushBack(i)
}
max := sum[qmax.Front().Value.(int)]
L := 0
for ; i < N; L, i = L 1, i 1 {
if qmax.Front().Value.(int) == L {
qmax.Remove(qmax.Front())
}
for qmax.Len() > 0 && sum[qmax.Back().Value.(int)] <= sum[i] {
qmax.Remove(qmax.Back())
}
qmax.PushBack(i)
max = getMax(max, sum[qmax.Front().Value.(int)]-sum[L])
}
for ; L < N-1; L {
if qmax.Front().Value.(int) == L {
qmax.Remove(qmax.Front())
}
max = getMax(max, sum[qmax.Front().Value.(int)]-sum[L])
}
return max
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
func getMax(a int, b int) int {
if a > b {
return a
} else {
return b
}
}执行结果如下：
图片左神java代码
