最大子序和
給定一個(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蛹稍。
動(dòng)態(tài)規(guī)劃
分析
1.首先對(duì)數(shù)組進(jìn)行遍歷，當(dāng)前最大連續(xù)子序列和為sum,結(jié)果為ans;
2.如果sum > 0,則說(shuō)明sum對(duì)最終結(jié)果有增益笔宿，則保留并加上當(dāng)前遍歷的元素;
3.如果sum <= 0,則說(shuō)明sum無(wú)增益犁钟，需舍棄，重新更新為當(dāng)前遍歷的元素;
4.每次比較sum和ans的大小泼橘，將最大值置為ans涝动，循環(huán)結(jié)束返回ans;
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
}
分治法
分析
將數(shù)組一分為二，那么最大子序和出現(xiàn)的位置有三種情況炬灭，1.左邊醋粟，2.右邊，3.橫跨中間重归。其中左右兩邊的情況可以遞歸處理米愿，最后返回三種情況的最大值。
class Solution {
public int maxSubArray(int[] nums) {
return __maxSubArray(nums, 0, nums.length - 1);
}
static int __maxSubArray(int[] nums, int start, int end){
if(start == end)
return nums[start];
if(start > end)
return Integer.MIN_VALUE;
int mid = (start + end) / 2;
//遞歸計(jì)算左半邊最大子序和
int max_left = __maxSubArray(nums, start, mid - 1);
//遞歸計(jì)算右半邊最大子序和
int max_right = __maxSubArray(nums, mid + 1, end);
//計(jì)算中間最大子序和
int max_mid = nums[mid];
int sum = nums[mid];
for(int i = mid - 1; i >= start; i--){
sum += nums[i];
max_mid = Math.max(sum, max_mid);
}
sum = max_mid;
for(int i = mid + 1; i <= end; i++){
sum += nums[i];
max_mid = Math.max(sum, max_mid);
}
//返回三種情況中的最大值
return Math.max(Math.max(max_left, max_right), max_mid);
}
}
