首页 > 代码库 > 【leetcode】Maximum Subarray

【leetcode】Maximum Subarray

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.

More practice:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 
在累加的过程中,如果发现sum<0则说明前面的序列对后面的序列没有贡献,故此时设置sum=0
 
 1 class Solution { 2 public: 3     int maxSubArray(int A[], int n) { 4         5         int sum,maxSum; 6         sum=maxSum=A[0]; 7         for(int i=1;i<n;i++) 8         { 9             if(sum<0) sum=0;10             sum+=A[i];11            12             if(maxSum<sum) maxSum=sum;13         }14         return maxSum;       15     }16 };

 

采用分治法求解:
找到左半边最大的序列值,找到右半边最大的序列值,找到中间序列的值
 
 1 class Solution { 2 public: 3     int maxSubArray(int A[], int n) { 4         5         divideAndConquer(A,0,n-1); 6     } 7     8     int divideAndConquer(int A[],int left,int right) 9     {10        11         if(left==right) return A[left];12  13         int mid=(left+right)/2;14        15        16         int leftMax=divideAndConquer(A,left,mid);17         int rightMax=divideAndConquer(A,mid+1,right);18        19         int midSum1=0;20         int midMax1=A[mid];21        22         for(int i=mid;i>=left;i--)23         {24             midSum1+=A[i];25             if(midMax1<midSum1) midMax1=midSum1;26         }27        28         int midSum2=0;29         int midMax2=A[mid+1];30        31         for(int i=mid+1;i<=right;i++)32         {33             midSum2+=A[i];34             if(midMax2<midSum2) midMax2=midSum2;35         }36        37         int midMax=midMax1+midMax2;38        39         return max(max(leftMax,rightMax),midMax);40        41        42     }43 };

 

【leetcode】Maximum Subarray