Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
101 lines (80 sloc) 3.14 KB
layout title date categories
post
数组中的连续元素的最大和
2018-04-08 15:00:05 +0800
算法

分治法

设数组左边界为 lo,右边界为 hi,即 data[lo]...data[hi],可以计算出中点下标为:mid = (hi+lo)/2

数组中的连续元素的最大和一共有三种情况:

  1. data[lo:mid] 中,也就是在左子数组中
  2. data[mid+1:] 中,也就是在右子数组中
  3. data[x:y] 中,其中 x<=mid<=y 也就是跨越左右子数组

可以看出在上述情况中,问题可以分解为更小的子问题来解决,在原算法复杂度高于 O(n) 时,分治法可以提高时间效率,但是需要话费更大的空间,因为需要递归栈。

撸起袖子写代码:

func MaxSubArrayDivideAndConquer(data []int) int {
    if len(data) == 0 {
        return math.MinInt32
    }
    mid := len(data) / 2
    // 计算跨越中介的最大子数组
    midmax, sum := math.MinInt32, 0
    for i := mid; i >= 0; i-- {
        sum += data[i]
        if sum > midmax {
            midmax = sum
        }
    }
    for j := mid + 1; j < len(data); j++ {
        sum += data[j]
        if sum > midmax {
            midmax = sum
        }
    }
    // 计算左数组中的最大值
    l := MaxSubArrayDivideAndConquer(data[:mid])
    // 计算右数组的最大值
    r := MaxSubArrayDivideAndConquer(data[mid+1:])
    var max int
    if l > r {
        max = l
    } else {
        max = r
    }
    if midmax > max {
        max = midmax
    }
    return max
}

T(n) = T(n/2) + n

  • 时间复杂度:O(nlog(n))
  • 空间复杂度:O(log(n)

其中 log(n) 为递归栈的深度,在递归树中,每一层都需要计算 n 个元素之和。

线性方法

解决该问题还有一种效率更高的方法:

每一个下标 j 都有可能是最大子数组的结束下标,计算以 j 结尾的最大子数组之和,只需要知道以 j-1 结尾的最大子数组之和就可以,公式表达为:

m[j] = max(0, max[j-1]) + data[j]

算法实现:

func MaxSubArrayLinear(data []int) int {
    max, leftSum := math.MinInt32, math.MinInt32
    for i := 0; i < len(data); i++ {
        if leftSum <= 0 {
            leftSum = 0
        }
        leftSum += data[i]
        if leftSum > max {
            max = leftSum
        }
    }
    return max
}
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

好的算法实现起来往往是简单的,在时间和空间效率上更高

总结

最近笔试各大公司在最后算法题总是不能 AC,也在跟着这个仓库 刷 leetcode 题目。

最近很大的感受是,只有把思路理清楚后再写代码,即使是在笔试或者面试时候,不然逻辑上不可能有正确的代码,如果逻辑上(算法)本来就是错误的,用再多时间去写代码也是浪费时间而已。我之前就是还没理清思路就写代码,使得代码越来越丑(判断边界条件的代码越来越多),到后面调试的时候非常痛苦,当然凌乱的逻辑最后往往也是不能够 AC 的。