53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
- 1-暴力：n^2
- 2-DP：
a.分治（子问题）max_sum(i) = Max(max_sum(i - 1), 0) + a[i]
b.状态数组:f[i]
c.DP方程:f[i] = Max(f[i - 1] , 0) + a[i]
dp问题：
dp公式：dp[i] = max(nums[i] , nums[i] + dp[i - 1])
提取出nums[i] ：dp[i] = max( 0 , dp[i - 1]) + nums[i]
//nums[i - 1]代表dp[i - 1]
nums[i] = max(0 , nums[i - 1]) + nums[i]最大子序和 = 当前元素自身最大（负的），或者 包含之前（正的）后最大
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length]; // 存储以i为结尾的最大子序列和
dp[0] = nums[0]; // 第0个元素最大序列和为nums[0]
int maxSum = nums[0]; // 最大子序列和
// 遍历整个素组，获取以i为结尾的最大子序列和
// 当dp[i-1]>0时，dp[i]=nums[i]+dp[i-1]
// 当dp[i-1]<=0时,dp[i]=nums[i]
for (int i = 1; i < nums.length; i++) {
if (dp[i - 1] > 0) {
dp[i] = dp[i - 1] + nums[i];
} else {
dp[i] = nums[i];
}
// 每次比较dp[i]和maxSum取最大值
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
简化if else 判断：
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length]; // 存储以i为结尾的最大子序列和
dp[0] = nums[0]; // 第0个元素最大序列和为nums[0]
int maxSum = nums[0]; // 最大子序列和
// 遍历整个素组，获取以i为结尾的最大子序列和
// 当dp[i-1]>0时，dp[i]=nums[i]+dp[i-1]
// 当dp[i-1]<=0时,dp[i]=nums[i]
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(0, dp[i - 1]) + nums[i];
// if (dp[i - 1] > 0) {
// dp[i] = dp[i - 1] + nums[i];
// } else {
// dp[i] = nums[i];
// }
// 每次比较dp[i]和maxSum取最大值
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
不新增dp数组，直接使用nums数组
public int maxSubArray(int[] nums) {
int maxSum = nums[0]; // 最大子序列和
for (int i = 1; i < nums.length; i++) {
nums[i] = Math.max(0, nums[i - 1]) + nums[i];
maxSum = Math.max(maxSum, nums[i]);
}
return maxSum;
}
对于上面的代码，也可以使用lastSum来记录nums[i-1]为结尾的最大连续子序列和
public int maxSubArray(int[] nums) {
int maxSum = nums[0]; // 最大子序列和
int lastSum = nums[0];//假设当前索引为i,则lastSum保存以nums[i-1]为结尾的最大连续子序列和
// 遍历整个素组，获取以nums[i]为结尾的最大子序列和
for (int i = 1; i < nums.length; i++) {
lastSum = Math.max(0, lastSum) + nums[i];
maxSum = Math.max(maxSum, lastSum); // 每次比较lastSum和maxSum取最大值
}
return maxSum;
}
