动态规划之最大子序和
示例：
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
解析:利用动态规划思想。假设i-1的最大子序和已经求出为dp[i-1],那么如果dp[i-1]小于0，第i个为结尾的最大子序和不如不加，因为前面i-1最大子序加出来都是负的，直接将nums[i]作为dp[i]。如果dp[i-1]大于0，那么证明前面的子序和不小，可以跟着一起做更大的。最大子序和要每次都和更新了的maxSum比大小。
代码:
class Solution {
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
int maxSum = nums[0];
for(int i = 1;i<nums.length;i++){
if(dp[i-1] < 0){
dp[i] = nums[i];
}else{
dp[i] = dp[i-1]+nums[i];//状态转移方程
}
maxSum = Math.max(maxSum,dp[i]);
}
return maxSum;
}
} 
查看19道真题和解析