Maximum Subarray
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
.
click to show more practice.
解題思路:
題意為找出連續的和最大的子數組的和。可以有兩種方法來做,動態規劃以及分治法。
1、動態規劃。求最值問題一般可以考慮動態規劃的方法。d[i]表示子數組nums[k, i]的最大值,其中k>=0並且k
d[i] = nums[i], i==0 或者 d[i-1]<0 d[i] = nums[i] + d[i-1], 其他
然後返回d[]數組的最大值即可。這種方法的空間復雜度為O(n),其實可以優化成O(1)的空間復雜度。時間復雜度為O(n)
class Solution { public: int maxSubArray(vector& nums) { int len = nums.size(); if(len<1){ return 0; } int d[len]; d[0]=nums[0]; int maxSum=nums[0]; for(int i=1; i 0){ d[i]=nums[i]+d[i-1]; }else{ d[i]=nums[i]; } maxSum = max(d[i], maxSum); } return maxSum; } };
(1)最大值子數組在mid前面
(2)最大值子數組在mid後邊
(3)最大值子數組跨過mid
對於(1)(2),可以直接用遞歸來求得,對於(3),我們以mid向兩邊延伸找到最大的和。然後返回三種情況最大的一項即可。
空間復雜度為O(1),時間復雜度為O(n)
class Solution { public: int maxSubArray(vector& nums) { return maxSub(nums, 0, nums.size() - 1); } int maxSub(vector & nums, int left, int right){ if(left>right){ return INT_MIN; } int mid = (left + right) / 2; int lMax = maxSub(nums, left, mid - 1); int rMax = maxSub(nums, mid + 1, right); int sum = 0; int lMaxSub = 0; for(int i=mid - 1; i>=left; i--){ sum += nums[i]; lMaxSub = max(sum, lMaxSub); } int rMaxSub = 0; sum = 0; for(int i=mid + 1; i<=right; i++){ sum += nums[i]; rMaxSub = max(sum, rMaxSub); } return max(max(lMax, rMax), lMaxSub + rMaxSub + nums[mid]); } };