2021-04-25: given an array arr and a positive number m, the

Fuda answer 2021-04-25：

The prefix and + Double ended queues with large left and small right . It's too late , So it's simple .

The code to use golang To write . The code is as follows ：

package main

import (
    "container/list"
    "fmt"
)

func main() {
    arr := []int{1, 2, -3, 4, -5}
    ret := maxSum(arr, 5)
    fmt.Println(ret)
}

// O(N) Solution method , Optimal solution 
func maxSum(arr []int, M int) int {
    if len(arr) == 0 || M < 1 {
        return 0
    }
    N := len(arr)
    // The prefix and 
    sum := make([]int, N)
    sum[0] = arr[0]
    for i := 1; i < N; i++ {
        sum[i] = sum[i-1] + arr[i]
    }

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

The results are as follows ：

picture

---

Zuo Shen java Code