求元素累加和最大的子数组

问题描述

对于一个给定的整数数组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]
}

求元素累加和最大的子数组》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.