Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
思路：dp
dp[i]表示一a[i]结尾的最大子数组的和
dp[i]=max(dp[i-1]+a[i],a[i]);
AC代码
public class Solution {
public int maxSubArray(int[] nums) {
int n=nums.length;
int dp[]=new int[n];
dp[0]=nums[0];
int answer=dp[0];
for(int i=1;i<n;i++){
dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
answer=Math.max(dp[i],answer);
}
return answer;
}
}
