前言
最近工作不是特别忙，是以有更多時間來學習算法相關知識，補短處。題目來源于leetcode，通過一個算法題，我們去分析該算法題所屬類型，以及解題思路，以及該算法題所用到的數學知識。選擇的算法題目從容易到困難，逐漸提高難度，解題的思路也是從簡單到複雜，時間複雜度也是從低到高的順序來書寫這個系列的部落格。因工作語言和使用熟練度原因算法采用Java編寫，但該系列中可能會穿插c、C++、python語言實作，請不要奇怪。
題目
分析題目：給定的整型數組，求解最大連續子數組和，要求是至少包含一個元素，且算法時間複雜度至少O(n).
首先我們想到就是：計算所有子數組的和進行比較取最大值，該方式叫做暴力求解，如果在資料規模很小的情況下我們就可以很輕松的接觸結果，但一旦 規模稍微大一些，其性能就及其低了。那麼我們先來寫一下暴力求解算法實作。
暴力求解算法
// 1.暴力解析 private static int maxSubArrayByVoilence(int[] nums) { if(nums.length == 1){ return nums[0]; } int currentSubSum,maxSubSum=nums[0]; // 思路: 1.暴力破解。周遊子數組的和進行比較 for(int i =0; i < nums.length; i++){ for (int j = i; j < nums.length; j++){ // 目前子數組和 currentSubSum = 0; for (int k = i; k <= j; k++){ currentSubSum += nums[k]; } // 比較最大值與目前子數組和 if(currentSubSum>maxSubSum){ maxSubSum = currentSubSum; } } } return maxSubSum; } 分析：該解題方法的時間複雜度為O(n^3).效率非常低，但邏輯非常簡單。針對暴力破解算法，我們可以考慮進行優化，使其時間複雜度降低為O(n^2),因為簡單是以不再這裡多寫，同時也留給讀者自行編寫，如果可以你可以留言下來給其他讀者或者給我看，看看你的優化思路。
最大連續子數組問題讓我想到了《資料結構與算法》中的一個名詞：最優解問題。該類問題就是屬于最優解類型的題目，是以我們可以通過最優解問題的解題思路來解決這個算法題目：動态規劃算法。
動态規劃算法
動态規劃算法-百度詞條
動态規劃算法的基本思想與分治法類似，也是将待求解的問題分解為若幹個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的資訊。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丢棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
由于動态規劃解決的問題多數有重疊子問題這個特點，為減少重複計算，對每一個子問題隻解一次，将其不同階段的不同狀态儲存在一個二維數組中。
上面是百度詞條的解釋，了解起來不難，那麼我們這個問題，該如何實作算法呢？廢話不多說，代碼先撸出來。
// 3.動态規劃 private static int maxSubArrayByDP(int[] nums) { if(nums.length == 1){ return nums[0]; } int maxSubSum = nums[0],currentSubSum = nums[0]; for(int i=1;i<nums.length;i++){ currentSubSum += nums[i]; // 如果加上nums[i]後反而更小了，則從nums[i]開始重新計算 if(currentSubSum < nums[i]){ currentSubSum = nums[i]; } // 比較大小 if(currentSubSum > maxSubSum){ maxSubSum = currentSubSum; } } return maxSubSum; } 分析：動态規劃算法時間複雜度為O(n),相比較于暴力解法效率就大大提升了。關鍵點在于如果加上nums[i]後相比較nums[i]小，那麼說明i之前和比i數值小，是以既然比之前小，那麼就可以把前面的都抛開重新規劃計算和。
動态規劃的數學表達：currentSubSum(i)表示數組下标以i為起點的最大連續下标最大的和，而maxsum(i)表示前i個元素的最大子數組之和。那麼我們就可以推出下一個maxsum(i+1)應該為cursum(i+1)和maxsum(i)中選取一個最大值。遞推式為：
currentSubSum(i) = max{A[i],currentSubSum(i-1)+A[i]};
maxSubSum(i) = max{maxsum(i-1),currentSubSum(i+1)};
根據follow up的說明，還可以使用分治法去求解這個算法題。那麼我們接下來看看分治法如何實作這個算法。
分治算法
// 4.分治算法+遞歸 private static int maxSubArrayByDC(int[] num, int low, int high) throws Exception { // 終止條件 if(low==high) return num[low]; else if(low<high) { int mid = (low+high)/2; // 左側最大子數組和計算 int left = maxSubArrayByDC(num,low,mid); // 右側最大子數組和計算 int right = maxSubArrayByDC(num,mid+1,high); // 跨越分區子數組和計算 int sum=0,max=0,i=0,j=0,center=0; for(i=mid;i>=low;i--) { sum+=num[i]; if(sum>max) { max = sum; } } center+=max; max = -1; sum=0; for(j=mid+1;j<=high;j++) { sum+=num[j]; if(sum>max) { max = sum; } } center+=max; j = left>=right?left:right; j = j>=center?j:center; return j; }else { // 抛出異常 throw new Exception("索引值錯誤，low值一定不能比high值大"); } } 分析:分治法處理規模大的問題時，采用的是縮小規模，然後比較各個規模的結果，進而得出最終結果。分治法的時間複雜度為O(nlogn)這裡關鍵是了解分治思想，對于分治思想，我從網上找了一張圖檔，如下，能夠很好的幫助我們了解和記住這種思維方式。
總結
該算法題雖然是很簡單的一道題目，但包含的算法思想非常優秀。該系列的文章，我會陸續的寫一些題目的解法，但不會所有LeetCode題目都寫，我選擇題目的要求是：有意思（包括多種有意思的解題算法，或者我不懂的算法）的，有技巧的，有深度的。如果你對這題有更多想說的可以在下面留言和讀者讨論，我也會一起參與的喲。