问题描述

对于一个给定的整数数组arr[0...n)，求这样一个子数组，它的元素的累加和在所有子数组中是最大的。

这个题在《编程珠玑》一书中有介绍，以前也是在这本书上看到解决方法后就再也没有忘记了。现在重新实现并记录一下，记录了从最低效的3重循环解决方法到最高效的线性时间解决方法及其中的优化考量。

3重循环

最直接的想法是用3重循环，计算每个子数组的和，这样的效率太低了。

实现

func SubSeqHasMaxSum3Loop(arr []int) []int {
    mSum, mL, mR := arr[0], 0, 0
    for i, limit := 0, len(arr); i < limit; i++ {
        for j := i; j < limit; j++ {
            sum := 0
            for k := i; k <= j; k++ {
                sum += arr[k]
            }
            if sum > mSum {
                mSum = sum
                mL = i
                mR = j
            }
        }
    }
    return arr[mL : mR+1]
}

2重循环

一个优化点是：假如当前一个子数组为arr[l...r]，其累加和为sum，那么子数组arr[l...r+1]的累加和可以通过sum+arr[r+1]得到。

这样可以把3重循环优化为2重循环。

实现

func SubSeqHasMaxSum2Loop(arr []int) []int {
    mSum, mL, mR := arr[0], 0, 0
    for i, limit := 0, len(arr); i < limit; i++ {
        sum := 0
        for j := i; j < limit; j++ {
            sum += arr[j]
            if sum > mSum {
                mSum = sum
                mL = i
                mR = j
            }
        }
    }
    return arr[mL : mR+1]

线性时间解决

上面的2重循环并不是最优的，这个线性时间解决方法仍然与前面的优化方案有关。

先来看下整数对于加法的作用：对于一个整数i，如果 i > 0，那么它会让累加和增加；如果 i < 0，它会让累加和减少；i==0对累加和没有影响。

• 如果当前可能的目标子数组的累加和sum <= 0，那么不管接下来的元素v的值如何，它对可能的目标子数组的累加和都是负作用或无作用的，可以安全地排除当前可能的目标子数组，而把下一个元素作为可能的目标子数组。

• 如果当前可能的目标子数组的累加和sum > 0，那么不管接下来的元素v的值如何，可以直接把它纳入当前可能的目标子数组，因为即使v < 0，也可能有更后面的元素是大于元素v的绝对值的，从而抵消了元素v的副作用。

实现

func SubSeqHasMaxSum(arr []int) []int {
    if arr == nil || len(arr) < 1 {
        return []int{}
    }

    maxSum, mL, mR, sum, l, r := arr[0], 0, 0, arr[0], 0, 1

    for limit := len(arr); r < limit; r++ {
        if sum <= 0 {
            sum = arr[r]
            l = r
        } else {
            sum += arr[r]
        }

        if sum > maxSum {
            maxSum = sum
            mR = r
            mL = l
        }
    }

    return arr[mL : mR+1]
}

欢迎关注我的微信公众号: coderbee笔记，可以更及时回复你的讨论。