使用动态规划法,定义一个dp数组记录从第一个数字开始到当前数字的最大累加和。
每当前一个累加和大于0时,进行dp[i]的更新。
最后遍历dp数组,取最大的dp[i]返回。
过程可以看注释:
public int maxsumofSubarray (int[] arr) { // write code here int len = arr.length; int res = 0; //用tmp数组记录从0出发到当前数字能累加的最大数 int[] dp = new int[len]; //先初始化它 for(int i=0; i < len; i++){ dp[i] = arr[i]; } //开始遍历 for(int i=1; i < len; i++){ //当前面已累加和大于0时,加上肯定比当前的数字大 dp[i] = (dp[i-1] > 0 ? (dp[i-1]+ arr[i]) : dp[i]); } //进行比较,选择出最大的累加和 for(int i=0; i < len; i++){ res = Math.max(res, dp[i]); } return res; }