Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array
the contiguous subarray
[−2,1,−3,4,−1,2,1,−5,4]
,the contiguous subarray
[4,−1,2,1]
has the largest sum = 6
.
Solution 1: Use DP, max is current max value at i and then keep updating the final result.
public class Solution {
public int maxSubArray(int[] nums) {
int n=nums.length;
int max=0, res=0;
for (int i=0; i<n; i++) {
if (i==0) {
max=nums[0];
res=nums[0];
}
else {
max=(max>0)?max+nums[i]:nums[i];
res=Math.max(res,max);
}
}
return res;
}
}
没有评论:
发表评论