/**DP * @param nums * @return the max sum of sub array */ publicintmaxSubArray(int[] nums) { int dp[] = newint[nums.length]; dp[0] = nums[0]; intmaxSum= dp[0]; for (inti=1; i < nums.length; i++) { if (dp[i - 1] > 0) { dp[i] = dp[i - 1] + nums[i]; } else { dp[i] = nums[i]; } maxSum = Math.max(dp[i], maxSum); } return maxSum; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/**Find the law * @param nums * @return the max sum of sub array */ publicintmaxSubArray(int[] nums) { intmaxSum= Integer.MIN_VALUE; intcurSum=0; for (inti=0; i < nums.length; i++) { curSum = (curSum <= 0) ? nums[i] : (nums[i] + curSum); maxSum = Math.max(maxSum, curSum); } return maxSum; }