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
    }
}