#53. Maximum Subarray
題目描述
給你一個整數陣列nums，找到其中一段具有最大總和的子陣列，並且會回傳它的總和。
限制條件
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
解題思路
Dynamic Programming
當處於最大值區間時，從該區間的起點到終點全部加起來就是最大值，因此當前總和如果小於0，則不會是目標區間，並且從下一個元素開始重新重0開始加總，直到獲得最大值。
public class Solution {
public int MaxSubArray(int[] nums) {
int max = Int32.MinValue;
int sum = 0;
foreach(int i in nums){
sum += i ;
max = Math.Max(sum,max);
if(sum<0) sum=0;
}
return max;
}
}
複雜度分析：
- 時間複雜度：O(n)
- 空間複雜度：O(1)
Follow-up
如果你找到O(n)的解答，試試看使用比較不直覺的分治法來解決。
Divide and Conquer
以最直覺的解法來找一個子陣列加總後的最大值，我們知道陣列是一個區間，假設我們在這個區間之間選一個點，向左延伸以及向右延伸，就會得到這個區間的邊界，而這裡的邊界就是總和最大值的區間。 因此，最暴力的方法就是從每一個位置開始向左右延伸檢查，全部檢查完畢後就會找到最大值的區間，但是這會花上O(N^2)的時間，因為每個左右延伸的檢查都會走完整個陣列。 但是這其中其實有一部分的檢查是重複的，所以只要減少這一部份的浪費時間檢查，就可以讓時間複雜度減少到可以滿足解決問題的條件。
分治法將陣列視為三個區間，陣列的左半區間、右半區間以及陣列的中間區間，中間區間橫跨了左區間和右區間，當我們在尋找區間最大值的時候，這個值可能落在左區間或者右區間，同時也可能落在包含左右區間的中間區間，透過區分這三個區間的策略，可以完整涵蓋最大值區間可能出現的範圍。
緊接著在這區間之中，左區間與右區間又可以各自拆分成三等份，假設最大值區間落在左區間中，為了更仔細的取得最大值的區間，用分治法再一次的將左區間拆分，就可以繼續向下進行劃分。
當不斷的進行分割區間到最後，就只會剩下一個元素的區間，這個元素就會成為最基本的答案候選之一，這個時候再往上去合併成區間值，去比較各自的區間值，返回其中最大的區間值，一直回到最上層，就會是題目所求的答案。
範例： [-2,1,-3,4,-1,2,1,-5]
-----------------拆分--------------- 拆分陣列長度 陣列 8 | [-2,1,-3,4,-1,2,1,-5] 第一層 4 | [-2,1,-3,4] [-1,2,1,-5] 第二層 2 | [-2,1] [-3,4] [-1,2] [1,-5] 第三層 1 | [-2] [1] [-3] [4] [-1] [2] [1] [-5] 第四層
--------------中間區間最大值------------- 中區間值： 6 8 | [-2,1,-3,4,-1,2,1,-5] 第一層 中區間值： 2 3 4 | [-2,1,-3,4] [-1,2,1,-5] 第二層 中區間值： 1 1 1 1 2 | [-2,1] [-3,4] [-1,2] [1,-5] 第三層 中區間值： -2 1 -3 4 -1 2 1 -5 1 | [-2] [1] [-3] [4] [-1] [2] [1] [-5] 第四層
Note: 左右區間值等於下一層的左、中、右三區間之中的最大值。
這個例子總共有四層，第四層沒有左右區間，第三層的左右區間是第四層的值，
從第二層開始的左右區間才會是第三層的左、中、右之間取最大值。
--------------左右區間值-------------
中區間值： 6
左右區間值： (左|右) 4 | 3
8 | [-2,1,-3,4,-1,2,1,-5] 第一層
︽ 向上合併，左、中、右取最大值
中區間值： 2 3
左右區間值： (左|右) 1 | 4 2 | 1
4 | [-2,1,-3,4] [-1,2,1,-5] 第二層
︽ 向上合併，左、中、右取最大值
中區間值： 1 1 1 1
左右區間值： (左|右) -2|1 -3|4 -1|2 1|-5
2 | [-2,1] [-3,4] [-1,2] [1,-5] 第三層
︽ 向上合併
中區間值： -2 1 -3 4 -1 2 1 -5
1 | [-2] [1] [-3] [4] [-1] [2] [1] [-5] 第四層
public class Solution {
public int MaxSubArray(int[] nums) {
return DivideAndConquer(nums, 0, nums.Length-1);
}
public int DivideAndConquer(int[] nums, int left, int right){
if(left == right) return nums[left];
int mid = left + (right-left)/2;
int leftPartMaxVal = DivideAndConquer(nums, left, mid);
int rightPartMaxVal = DivideAndConquer(nums, mid+1, right);
int midV = MidCrossingMaxValue(nums, left, right, mid);
return Math.Max(midV, Math.Max(leftPartMaxVal, rightPartMaxVal));
}
public int MidCrossingMaxValue(int[] nums,int left, int right, int mid){
int leftMaxVal = Int32.MinValue;
int leftSum = 0;
for(int i=mid;i>=left;i--){
leftSum+=nums[i];
leftMaxVal = Math.Max(leftMaxVal, leftSum);
}
int rightMaxVal = Int32.MinValue;
int rightSum = 0;
for(int i=mid+1;i<=right;i++){
rightSum+=nums[i];
rightMaxVal = Math.Max(rightMaxVal, rightSum);
}
return leftMaxVal+rightMaxVal;
}
}
複雜度分析：
- 時間複雜度：分治法會將陣列不斷的拆分到最小元素再處理，每拆分一次都會把數量拆成原本的兩倍，因此時間複雜度為O(n log n)。
- 空間複雜度：遞迴會將空間全部展開後再合併，因此空間複雜度為O(log n)。
學習重點
- 動態規劃
- 分治法