輸入一個整型數組，數組中的一個或連續多個整數組成一個子數組。求所有子數組的和的最大值。

要求時間復雜度為O(n)。

示例1:

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。

解題思路

對于一個數組，最大和的連續子數組可以由3種情況得來，設數組的中間元素為mid，mid元素把原數組分隔為了左右兩個部分

1. mid元素向左右兩邊找最大的連續子數組
2. 左部分數組的連續子數組的最大和
3. 右部分數組的連續子數組的最大和

因此，只需要選出這三個部分中的最大值即可

代碼

class Solution {public int maxSubArray(int[] nums) {return  div(nums,0,nums.length-1);}public int div(int[] nums,int l,int r) {if (l>r) return 0;int mid=(r-l)/2+l;int left=div(nums, l, mid-1),right=div(nums, mid+1, r);int lMax=0,rMax=0,lSum=0,rSum=0;for (int i=mid-1;i>=l;i--){lSum+=nums[i];lMax= Math.max(lMax,lSum);}for (int i=mid+1;i<=r;i++){rSum+=nums[i];rMax= Math.max(rMax,rSum);}int res=lMax+rMax+nums[mid];if(l<=mid-1)res= Math.max(res,left);if(r>=mid+1)res=Math.max(res,right);return res;}
}