题解 | #连续子数组的最大和#

jz30 连续子数组的最大和

题意分析

找出数组中连续部分的最大和。

示例输入：input = [1,-2,3,10,-4,7,2,-5]
返回：18
解释：input数组有多个连续子数组，如[1,-2,3]，[3,10,-4,7,2]。在输入数组的所有子数组中，子数组的最大和为18，该数组为[3,10,-4,7,2]。

题解一（暴力）：

我们将所有的子数组都求出来，求出他们的和，找出最大的和。

int FindGreatestSumOfSubArray(vector<int> array) {
    int ret = INT_MIN;
    for (int i = 0; i < array.size(); i++) {
        int sum = 0;
        for (int j = i; j < array.size(); j++) {
            sum += array[j];
            ret = max(ret, sum);
        }
    }
    return ret;
}

时间复杂度： $O(n^2)$ 。可以被ac。

空间复杂度： $O(1)$ 。没有申请额外的数组空间。

题解二（动态规划）

在题解一中，我们求得了所有子数组的和，然后比较的出了他们的最大值。比如在计算sum[1...10]，我们在之前计算过sum[0...1]，sum[0...10]。sum[1,10]，很明显可以通过前面两个计算得到有没有办法避免一些重复计算。这里使用动态规划。

我们假设dp[j]表示从0到j之间最大的子数组和，注意这个子数组一定要包含array[j]。怎么么求得dp[j]呢？想象一下，如果你已经求得了dp[j-1]，怎样得到dp[j]。很明显，只要加上什么时候应该加上array[j]即可。

当dp[j-1] $\leq$ 0时，由于我们一定要选择array[j]作为子数组的一部分，那么dp[j]=array[j]。

当dp[j-1] $>$ 0时，由于我们一定要选择array[j]作为子数组的一部分，那么dp[j]=dp[j-1]+array[j]。

$dp[j]=\left\{\begin{matrix} dp[j-1]+array[j], dp[j-1]>0\\ array[j],dp[j-1]<=0 \end{matrix}\right.$

之后根据上述方程写出算法即可。

int FindGreatestSumOfSubArray(vector<int> &array) {
    vector<int> dp(array.size(), 0);
    dp[0] = array[0];
    int ret = dp[0];
    for (int i = 1; i < array.size(); i++) {
        dp[i] = max(dp[i - 1] + array[i], array[i]);
        ret = max(ret, dp[i]);
    }

    return ret;
}

时间复杂度： $O(n)$ 。遍历了一遍数组。

空间复杂度： $O(n)$ 。额外申请了长度为n的向量