最大子数组问题

问题描述：

给定一个数组A[]，求其子数组之和的最大值：
$$
max{ \sum _{i = l}^{r} A[i], 0 \le l \le r \le n-1}
$$

1. 暴力方法：O(n)

找出所有的子数组并且分别计算其和。一共有$C_22^)

  1. int[n][n] sum;
  2. int maxSubArray(left, right) {
  3.     if (!sum[left][right].exist())
  4.         maxSubArray[left][right] = maxSubArray(left + 1, right - 1)
  5.                                     + A[left] + A[right];
  6.     return sum[left][right];
  7. }

2. 分治策略: O(nlogn)

首先将一个数组分为[left,mid]和[mid + 1, right]两部分
最大子数组只可能有这些情况：

  • 在左子数组中
  • 在右子数组中
  • 横跨两个子数组

那么，求解的算法为：

// 分治算法求解最大子数组
int maxSubArray(left, right) {
    int mid = (left + right) / 2;
    return max(
        maxSubArray(left, mid),                // 在左子数组中
        crossMidSum(left, right, mid),        // 横跨在中间
        maxSubArray(mid + 1, right)            // 在右子数组中
    );
}

算法的关键是求解横跨在中间的最大子数组crossMidSum()

// 求解横跨在中间的情况
int crossMidSum(left, right, mid) {
    int leftMax = rightMax= _INTMIN_;
    int leftSum = rightSum = 0;
    for (int i: mid down_to left)        // (<-| mid
        leftMax = (leftSum += A[i]) > leftMax ? leftSum : leftMax;
    for (int i: mid to right)            // mid |->)
        rightMax = (rightSum += A[i]) > rightMax ? rightSum : rightMax;
    return leftMax + rightMax;
}

可以看到，crossMidSum这个函数的时间复杂度为O(right - left)，是O(n)的
分治策略的总时间代价为：T(n) = 2T(n/2) + O(n)。化简为O(nlogn)

3. 动态规划：O(n)

这种算法可以将时间开销降低到线性
A[0...j+1]的最大子数组只有这些情况：

  • 要么是A[0...j]的最大子数组
  • 要么是某个子数组A[i...j+1] ``` maxSub[j + 1] = max{ maxSub[j], // A[0…j]的最大子数组 maxSubRight[j + 1] // 子数组A[i…j+1] }
`A[0...j+1]`中包含`A[j+1]`的子数组`A[i...j+1]`该如何得到？<br />同样可以使用动态规划的思路

maxSubRight[j + 1] = max{ A[j + 1] + maxSubRight[j], A[j + 1] }

``` 这样，总体复杂度就成了O(n)了