題目要求

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

即：尋找數列中的一個子數列，該數列中的值得和是所有子數列中最大的。

思路一：divide&conquer

我們可以從數列的中間節點將數列分為兩個子數列，則最大的子數列要么在左子列，要么在右子列，要么跨越了左子列和右子列。我們可以分別得出這三種情況下的最大子數列和，并比較得出最大的那個。
divide&conquer即遞歸思路，將復雜問題分解為簡單的小問題分別解決。遞歸的重點在于覆蓋所有可能情況，并且覆蓋到基類。

    public int maxSubArray(int[] nums) {int start = 0;int end = nums.length - 1;return maxSubArray(nums, start, end);}//遞歸調用該方法public int maxSubArray(int[] nums, int start, int end){if(start==end){return nums[start];}int mid = (start + end) / 2;//獲得最大左子列int leftMax = maxSubArray(nums, start, mid);//獲得最大右子列int rightMax = maxSubArray(nums, mid+1, end);//獲得最大中子列int leftSumMax = Integer.MIN_VALUE;int temp = 0;do{temp += nums[mid];if(temp>leftSumMax){leftSumMax = temp;}}while((--mid)>=start);temp = 0;mid = (start + end)/2 + 1;int rightSumMax = Integer.MIN_VALUE;do{temp += nums[mid];if(temp>rightSumMax){rightSumMax = temp;}}while((++mid)<=end);int midMax = leftSumMax + rightSumMax;return Math.max(Math.max(leftMax, rightMax), midMax);}

思路二：divide&conquer2 recursion

上面是將數組從中劃分為兩個子數組,這里我們還可以劃分為nums[n-1]和nums[n]。這樣我們就可以將右子列的情況簡化為直接返回右子列的值。我們只需要考慮左子列的最大和以及跨越了左右的中子列的最大值。所以我們需要記錄兩個值，第一個是當前最大和，還有一個是到nums[n-1]的最大子列和。

    public int maxSubArray(int[] A) {int n = A.length;//存儲經過下標為i的最大子數列和，用于判斷中子列int[] dp = new int[n];dp[0] = A[0];int max = dp[0];for(int i = 1; i < n; i++){dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);max = Math.max(max, dp[i]);}return max;    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~