《剑指Offer》连续子数组的最大和

题目描述：

  HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。

但是,如果输入一个整型数组，数组里有正数也有负数。数组中一个或者连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}和最大的子数组为{3, 10, -4, 7, 2},因此输出为该子数组的和18

解题思路：

数组分析：下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。通过分析我们发现，累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始。

过程如下：

代码实现(c++)

class Solution {
public:
    int findGreatestSumOfSubArray(vector<int> array) {
        if(array.empty()){
            return 0;
        }
        // 初始化变量，maxSum为最大和，curSum为当前和
        int maxSum = array[0];
        int curSum = array[0];
        // 遍历所有元素
        for(int i = 1; i < array.size(); i++){
            // 如果当前和小于等于0，说明之前的是负数，则抛弃前面的和，重新计算
            if(curSum <= 0){
                curSum = array[i];
            }
            // 如果没有问题，直接累加
            else{
                curSum += array[i];
            }
            // 更新最大和
            if(curSum > maxSum){
                maxSum = curSum;
            }
        }
        return maxSum;
    }
};

其他解法

方法一：贪心

因为时间复杂度为O(n)，则只能遍历一次数组
这里同时使用两个变量sum和res，其中sum保存的是当前的和
若sum<0，则从下一个位置从新记录，
res记录的是历史的最大值，只有当sum>res时用sum替换res。

class Solution {
public:
    int maxSubArray(vector<int>& array) {
        assert(!array.empty());

        int sum = array[0], res = array[0];

        for(int i = 1; i < array.size(); i++){
            sum >= 0 ? sum += array[i] : sum = array[i];
            if(sum > res) res = sum;
        }
        return res;
    }
};

方法二：动态规划 – Kadane算法 O(n)

在整个数组或在固定大小的滑动窗口中找到总和或最大值或最小值的问题，可通过动态规划(DP)在线性时间内解决。

本题可通过修改数组跟踪当前位置的最大和，在知道当前位置的最大和后更新全局最大和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        assert(!nums.empty());

        int sz = nums.size();
        int Max = nums[0];
        // 如果当前值小于0，重新开始（全局最大值更新）
        for(int i = 1; i < sz; ++i){
            // 更新当前最大值
            if(nums[i-1] > 0) nums[i] += nums[i-1];
            // 更新全局最大值
            Max = max(nums[i], Max);
        }
        return Max;
    }
};