描述
给定一个数组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),并没有使用额外的空间。
最后
这道题主用运用了动态规划的方式,每次选择最大值时需要通过比较当前值与当前值+之前最优解的值。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。