子数组的最大累加和问题
子数组的最大累加和问题
http://www.nowcoder.com/questionTerminal/554aa508dd5d4fefbf0f86e5fe953abd
- 既然是用动态规划，比较直观的思路是这样的：
对于一个给定的数组arr[0...n-1].利用一个辅助的数组s[0...n-1]去存储数组arr中结尾下标为i的最大子数组。那么有if(s[i-1]<=0) s[i] = arr[i]; else s[i] = s[i-1]+arr[i];
这样只需要在最后求s[i]的最大值即可。 - 但是这样空间复杂度为O(n)，为了满足题目要求，发现其实这个辅助的数组s[i]只与s[i-1]，也就是我们循环的当前值有关，所以只需要用一个变量去存储这个值即可。最终代码如下：
int maxsumofSubarray(int* arr, int arrLen ) { // write code here int cursor = arr[0]; int max = cursor; for(int i=1;i<=arrLen-1;i++){ if(cursor<=0) cursor = arr[i]; else cursor = arr[i]+cursor; if(max<=cursor) max = cursor; } return max; }
投递美团等公司10个岗位 >
查看20道真题和解析
