描述

给定一个数组arr，返回子数组的最大累加和
例如，arr = [1, -2, 3, 5, -2, 6, -1]，所有子数组中，[3, 5, -2, 6]可以累加出最大的和12，所以返回12.
题目保证没有全为负数的数据
[要求]
时间复杂度为O(n)O(n)，空间复杂度为O(1)O(1)

示例1

输入：
[1, -2, 3, 5, -2, 6, -1]

返回值：
12

思路

这道题有几个需要注意点：第一：题目要求是子数组的，我刚才做的时候就忽略了这点，导致怎么都不通过。。第二：是求的最大累加和。
以 示例一为例： [1, -2, 3, 5, -2, 6, -1]，如果我想求下标为 2的最大值改怎么求？是不是 下标为2也就是值为3 与 前面的最优解相加，然后看相加的结果是不是大于本身，如果大于那就有必要相加，如果小于，那么前面的值就可以舍弃掉，因为加了反而会拉低总和。
接下来看一下代码。

AC代码

public int maxsumofSubarray (int[] arr) {
        // write code here
        if (arr == null || arr.length < 1) {
            return 0;
        }
        // pre 当前节点前面的最优解， result 用来存储最终的结果
        int pre = 0, result = arr[0];
        for (int x : arr) {
            // 如果当前节点的值小于加上前面最优解的结果，那么就舍弃前面的只用当前的值
            pre = Math.max(x, pre + x);
            // 每次都去更新最大值
            result = Math.max(result, pre);
        }
        return result;
    }

时间复杂度：O(n),n 为数组长度
空间复杂度：O(1),并没有使用额外的空间。

最后

这道题主用运用了动态规划的方式，每次选择最大值时需要通过比较当前值与当前值+之前最优解的值。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。