2021-04-25：给定一个数组arr，和一个正数M，返回在arr的子数组在长度不超过M的情况下，求最大的累加和。

福大大 答案2021-04-25：

前缀和+左大右小的双端队列。时间太晚了，所以写得简单。

代码用golang编写。代码如下：

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代码