描述

给定一个数组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),并没有使用额外的空间。

最后

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

图片说明