连续子数组的最大和

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

//version1
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        if (array.size() == 0) {
            return 0;
        }
        //认为数组中第一个数值为最大值
        int result = array[0];
        //认为数组中第一个数组是需要返回的最大连续子向量的和
        int current_max = array[0];
        for (int i = 1; i < array.size(); i++)
        {   
            //如果之前连续子数组的局部最大和大于0，且当前数字大于0.
            if (current_max>=0&&array[i]>=0) {
                //更新当前连续子数组的局部最大值
                current_max = array[i]+ current_max;
                //如果当前连续子数组的局部最大值>当前保存结果最大值，更新最大值的结果。
                if (current_max > result) {
                    result = current_max;
                }
            }//如果当前值小于0，之前局部最小值小于0。求取两者最大值作为当前局部最大值
            else if(array[i]<0&&current_max<0)
            {
                current_max = current_max >array[i]?current_max:array[i];
            //如果当前局部最大值大于之前最大值，更新最大值结果。
                if (current_max > result) {
                    result = current_max;
                }
            }//如果当前值大于0，之前局部最大值小于0
            else if(array[i]>0&&current_max<0)
            {
                //更新当前最大值
                current_max = array[i];
            }//如果当前值小于0，之前局部最大值大于0。更新局部最大值的结果
            else if(array[i]<0&&current_max>0)
            {
                current_max = current_max + array[i];
            }
        }

        return result;
    }
};

//version2
class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        /*
        状态方程==>当前最大值为之前的最大值与当前值求和,当前值两者取最大值。
        Max(array[i])=max(Max(array[i-1])+array[i],array[i]);
        */
        if (array.size() == 0) {
            return 0;
        }
        int local_max = array[0];
        int result = array[0];

        for (int i = 1; i <array.size(); i++)
        {

            /*
            之前局部最大值与当前值进行比较

            1.如果之前局部最大值为正数，当前值为负数，则当前局部最大值为两者之和
            2.如果之前局部最大值为正数，当前值为正数，则当前局部最大值为两者之和
            3.如果之前局部最大值为负数，当前值为正数，则将当前值作为局部最大值
            4.如果之前局部最大值为负数，当前值为负数，则当前值、当前值+之前局部最大值，两者最大值作为新的局部最大值。
            */

            local_max = max(array[i], local_max + array[i]);
            if (local_max > result) {
                result = local_max;
            }
        }
        return result;
    }
};