连续子数组的最大和

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

题解：
对于此题，有两种方法。为暴力穷举和动态规划。
1）暴力穷举：
对于输入的数组，可以设置一个相同大小的数组，进行遍历。
对于一个长为n的输入，设置一个长为n的数组arr，而arr[0]表示为第0个数的值，arr[1]=array[1]+arr[0],即表示arr[1]为以第0个数为始，第1个数为终的子序列的和，arr[i]=array[i]+arr[i-1]表示以开始为0，终于i个数的子序列的和。
遍历更新始点不同、终点不同的子序列，最终得到穷举子序列中最大和。
代码如下：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        int res;
        if(array.size()==0)
            return 0;//返回长度为0的数组
        int *arr=new int[array.size()]{0};
        res=array[0];
        for(int i=0;i<array.size();i++){//遍历始点
            int temp=array[0];
            for(int j=i;j<array.size();j++){//遍历终点
                if(j==i){//更新点
                    arr[j]=array[j];
                    if(temp<arr[j])
                        temp=arr[j];
                }
                else{//更新数组数据
                    arr[j]=array[j]+arr[j-1];
                    if(temp<arr[j])
                        temp=arr[j];
                }
            }
            if(res<temp)
                res=temp;
        }
        delete[] arr;
        return res;
    }
};

2）动态规划：
从前往后进行遍历，对于第i个数，当前面序列相加的数据大于0时，则表示对最大值是有贡献的，如果是小于0，则表示相加会小于第i个数，对最大值没有贡献，并会减小。因此直接舍弃第i个数前面的数据，不断进行更新，得到最终答案。
代码如下：

class Solution {
public:
    int FindGreatestSumOfSubArray(vector<int> array) {
        /*int res;
        if(array.size()==0)
            return 0;
        int *arr=new int[array.size()]{0};
        res=array[0];
        for(int i=0;i<array.size();i++){
            int temp=array[0];
            for(int j=i;j<array.size();j++){
                if(j==i){
                    arr[j]=array[j];
                    if(temp<arr[j])
                        temp=arr[j];
                }
                else{
                    arr[j]=array[j]+arr[j-1];
                    if(temp<arr[j])
                        temp=arr[j];
                }
            }
            if(res<temp)
                res=temp;
        }
        delete[] arr;
        return res;*/
        int res;
        if(array.size()==0) return res;
        if(array.size()==1) return array[0];
        res=array[0];
        int num=array[0];
        for(int i=1;i<array.size();i++){
            num=max(num+array[i],array[i]);
            res=max(num,res);
        }
        return res;
    }
};