文章目錄
-
- 一、題目
- 二、解題
- 三、精妙的分治法
- 四、小結
一、題目
給定一個整數數組，找出總和最大的連續數列，并傳回總和。
示例：
輸入： [-2,1,-3,4,-1,2,1,-5,4]
輸出： 6
解釋： 連續子數組 [4,-1,2,1] 的和最大，為 6。
進階：
如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。
二、解題
起初做這道題的原因是想趁熱練習下歸并算法的相關題型，從分治算法專欄中選擇了這題，并且這題題目也說到可以用
精妙的分治法
求解。
讀完題之後， 大概有幾種思路， 暴力、貪心、分治。這次沒有嘗試暴力了，意義不大，主要在想如何用分治來解題，遺憾的是，一直沒有想清楚最有的數列區間如果是橫跨了左右兩個分治數列，該怎麼計算。最後選擇了貪心法解題。
貪心政策：負數不可能出現在一個總和最大的連續數列頭部
根據這個政策，我們隻需要周遊一次數列，對數組元素做累加， 碰到負數時重置總和記錄，從下一個元素繼續累加計數。記錄周遊過程中算出的最大總和的值。就是我們需要的最優解。
代碼如下：
class Solution {
public int maxSubArray(int[] nums) {
int sum = 0;
int maxSum = nums[0];
for(int i = 0; i < nums.length; ++i) {
if((sum + nums[i]) > 0 ) {
sum = sum + nums[i];
if(maxSum < sum) {
maxSum = sum;
}
} else {
// 這裡主要是為了相容整個數列都是負數時，能夠選出最小負數作為傳回值
if(maxSum < nums[i]) {
maxSum = nums[i];
}
sum = 0;
}
}
return maxSum;
}
}
執行結果：
三、精妙的分治法
雖然用貪心一次AC了， 但是沒有想到怎麼用分治解決還是不太爽，學習了一波題解。
正常來說，我們用分治可以将大數列的問題拆成子數列的問題，主要的問題點就是在知道了分治的左數組中的最大數列和以及右數組的最大數列和之後，額外的，還需要知道中間部分的最大數列和。然後，取三者的最大值，作為目前劃分子產品的最優解。分治完成後，我們就能得到全局最優解，時間複雜度就是分治法的時間複雜度 O(nlogn)。
實際上，這裡說的
中間部分的最大數列和
是需要每次分治過程中都進行計算的。也就是說，會需要多次對數組元素進行周遊才能求解。
代碼實作如下：
class Solution {
public int maxSubArray(int[] nums) {
return findMax(nums, 0, nums.length -1 );
}
// 傳回目前區間的最大連續和
private static int findMax(int[] nums, int lindex, int rindex) {
// 分到隻有一個元素時，傳回目前元素值
if(lindex == rindex) {
return nums[lindex];
}
// 記錄最大值
int max = Integer.MIN_VALUE;
// 計算中值
int mid = (lindex + rindex) / 2;
// 擷取左右部分的最大值
int sumLeft = findMax(nums, lindex, mid);
int sumRight = findMax(nums, mid + 1, rindex);
max = sumLeft > sumRight ? sumLeft : sumRight;
// 計算中間部分序列的最大值--以中間位置為起點，分别向左右周遊， 擷取左右區間的最大值，再取和即為中間部分的最大值
int maxLeft = nums[mid];
int maxRight = nums[mid + 1];
int sumLMid = 0;
int sumRMid = 0;
for(int i = mid; i >= lindex; --i) {
sumLMid = sumLMid + nums[i];
if (maxLeft < sumLMid) {
maxLeft = sumLMid;
}
}
for(int i = mid + 1; i <= rindex; ++i) {
sumRMid = sumRMid + nums[i];
if (maxRight < sumRMid) {
maxRight = sumRMid;
}
}
max = (maxLeft + maxRight) > max ? maxLeft + maxRight : max;
return max;
}
}
執行結果：
四、小結
這題來說， 貪心的時間複雜度 On 是要優于分治的。不過貪心的政策也稍微有點繞，不是很容易get到。然後就是分治算法現在自己能順利的一次寫下來也算是學習有所成效 ^ _ ^，加油打勞工！