题解 | #子数组的最大累加和问题#
子数组的最大累加和问题
http://www.nowcoder.com/practice/554aa508dd5d4fefbf0f86e5fe953abd
很难得的我也能快速写出来的DFS
一维dp传递
public int maxsumofSubarray (int[] arr) {
// write code here
int length = arr.length;
if(length==0) return 0;
if(length==1) return arr[0];
int[] dp = new int[length];
dp[0]=arr[0];
int max = dp[0];
for (int i = 1; i <length ; i++) {
dp[i]=Math.max(arr[i],arr[i]+dp[i-1]);
max=Math.max(max,dp[i]);
}
return max;
}
就算你真拿到牛友也会为你开心的