题解 | #子数组的最大累加和问题#毒瘤-贪心算法

func maxsumofSubarray(arr []int) int {
    // 负数过滤
    L, R := 0, len(arr)-1
    for arr[L] <= 0 {
        L++
    }
    for arr[R] <= 0 {
        R--
    }

    // 当前累加和数组
    sum := make([]int, R-L+1)
    sum[0] = arr[L]
    for i := L + 1; i <= R; i++ {
        sum[i-L] = arr[i] + sum[i-L-1]
    }

    max := sum[len(sum)-1]
    tmp := max
    // 两侧压缩 贪心
    for L != R {
        if arr[L] > arr[R] {
            tmp = tmp - arr[R]
            R--
        } else if arr[L] < arr[R] {
            tmp = tmp - arr[L]
            L++
        } else {
            m, n := L, R
            for m != n && arr[m] == arr[n] {
                if m+1 == n {
                    break
                }
                m++
                n--
            }
            if arr[m] > arr[n] {
                tmp = tmp - arr[R]
                R--
            } else {
                tmp = tmp - arr[L]
                L++
            }
        }
        if tmp > max {
            max = tmp
        }
    }
    return max
}