53. 最大子序和
給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）捅暴，返回其最大和伸眶。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大肛冶，為 6览徒。
進(jìn)階:
如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解呐舔。
- 1-暴力：n^2
- 2-DP：
a.分治（子問題）max_sum(i) = Max(max_sum(i - 1), 0) + a[i]
b.狀態(tài)數(shù)組: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]最大子序和 = 當(dāng)前元素自身最大（負(fù)的）币励，或者 包含之前（正的）后最大
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length]; // 存儲(chǔ)以i為結(jié)尾的最大子序列和
dp[0] = nums[0]; // 第0個(gè)元素最大序列和為nums[0]
int maxSum = nums[0]; // 最大子序列和
// 遍歷整個(gè)素組，獲取以i為結(jié)尾的最大子序列和
// 當(dāng)dp[i-1]>0時(shí)珊拼，dp[i]=nums[i]+dp[i-1]
// 當(dāng)dp[i-1]<=0時(shí),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;
}
簡(jiǎn)化if else 判斷：
public int maxSubArray(int[] nums) {
int[] dp = new int[nums.length]; // 存儲(chǔ)以i為結(jié)尾的最大子序列和
dp[0] = nums[0]; // 第0個(gè)元素最大序列和為nums[0]
int maxSum = nums[0]; // 最大子序列和
// 遍歷整個(gè)素組食呻，獲取以i為結(jié)尾的最大子序列和
// 當(dāng)dp[i-1]>0時(shí)，dp[i]=nums[i]+dp[i-1]
// 當(dāng)dp[i-1]<=0時(shí),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數(shù)組澎现，直接使用nums數(shù)組
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;
}
對(duì)于上面的代碼仅胞，也可以使用lastSum來記錄nums[i-1]為結(jié)尾的最大連續(xù)子序列和
public int maxSubArray(int[] nums) {
int maxSum = nums[0]; // 最大子序列和
int lastSum = nums[0];//假設(shè)當(dāng)前索引為i,則lastSum保存以nums[i-1]為結(jié)尾的最大連續(xù)子序列和
// 遍歷整個(gè)素組，獲取以nums[i]為結(jié)尾的最大子序列和
for (int i = 1; i < nums.length; i++) {
lastSum = Math.max(0, lastSum) + nums[i];
maxSum = Math.max(maxSum, lastSum); // 每次比較lastSum和maxSum取最大值
}
return maxSum;
}
