题解 | #子数组的最大累加和问题#
子数组的最大累加和问题
http://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd
可以进行累加判断，比如：1， -2， 3， 5， -2， 6， -1
对于第1个数，累加最大就是自己，1；
对于第2个数，累加最大为1+-2，即-1；
对于第3个数，累加最大就是自己，3；
对于第4个数，累加最大累加最大为3+5；
对于第5个数，累加最大。。。
故而可以使用动态规划解决，判断自己和上轮最大+自己谁大即可。
代码：
public int maxsumofSubarray (int[] arr) {
int len = arr.length;
int[] dp = new int[len];
int max = Integer.MIN_VALUE;
for (int i = 0; i < len; i++) {
if(i == 0) dp[i] = arr[i];
else{
dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
}
max = Math.max(dp[i], max);
}
return max;
}