题解 | #子数组的最大累加和问题#

NC19 子数组的最大累加和问题
参考Antrn的代码和想法！！！

题目描述
给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据

方法一：
解题思路
对于求解子数组的最大累加和，一开始想到，用双重循环来求解，外层控制子数组的长度，内层求解子数组的和，这样很轻松求出题目要求的最大累加和。（但是！这个时间复杂度就变成n的平方，而且当数组很长的时候，会由于时间的限制不会通过测试）
图片说明

解题代码

class Solution {//由于暴力循环，其时间复杂度为o(N^2),所以运行超时。
public:
    int maxsumofSubarray(vector<int>& arr) {
        int m=0;
        for(int i=1;i<=arr.size();i++)//这一层是子数组包含的个数
            for(int j=0;j<=arr.size()-i;j++)//第二层循环
            {
                int m1=0;
                for(int k=j;k<j+i;k++)m1+=arr[k];//一个小循环，计算子数组的和
                m = max(m,m1);
            }
        return m;
    }
};

复杂度分析
时间复杂度：由于是两层循环，因此时间复杂度为 $O$ ( $图片说明$ )，但超过了在线测试的时间限制，不可行。
空间复杂度：对于暴力求解，没有引入新的地址空间，因此空间复杂度为 $O(1)$

方法二：
解题思路
（借鉴Antrn的思想，动态规划）Antrn在求解这道题目的时候，就是对于子数组，在从头开始遍历的时候，只要我已有的数组在加上下一个数的时候不减，这样我就一直加，就这样，一层遍历，直接求出最大的数组。
图片说明
解题代码

class Solution {
public:
    int maxsumofSubarray(vector<int>& arr) {
        int m = arr[0]; // 保存最大累加和，在Antrn代码的基础上修改，然后通过第7个测试组
        for(int i = 1 ; i<arr.size() ; i++)
        {
            arr[i] = max(arr[i] , arr[i-1]+arr[i]);
            m = max(m, arr[i]);
        }
        return m;
    }
};

复杂度分析
时间复杂度：由于是一次遍历，因此时间复杂度为 $O(n)$
空间复杂度：和暴力求解一样，没有引入新的地址空间，因此空间复杂度为 $O(1)$