leetcode || 53、Maximum Subarray

problem:

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.

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.

Hide Tags   Divide and Conquer Array Dynamic Programming 題意：找出一個序列的最大和連續子序列

thinking:

（1）這道題解法特别多：

方法1：将每一個數和後一個數字相加，得到一個正負分布的序列，正數項對最大和子序列有用，作比較即可

方法2：暴力比對，兩層循環，調用max（）函數，時間複雜度O（n*n）,也可以算出結果，但是送出逾時

方法3：采用DP，時間複雜度O（n）

方法4：分治法，時間複雜度為nlog（n）

（2）本人實作了方法3 和方法4

code：

DP 法：

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int sum=A[0];
        int maxsum=A[0];
        for(int i=1;i<n;i++)
        {
            if(sum<0)    //DP核心
                sum=0;
            sum+=A[i];
            maxsum=max(sum,maxsum);
        }
        return maxsum;
    }


};
           

分治法：

class Solution {
public:
    int maxSubArray(int A[], int n) {
        int ret=maxsub(A,0,n-1);
        return ret;

    }
protected:
    int maxsub(int A[], int start, int end)
    {
        int max_left=INT_MIN,max_mid=INT_MIN,max_right=INT_MIN;
        if(start==end)
            return A[start];
        if(start+1==end)
        {
            int a=max(A[start],A[end]);
            return a>(A[start]+A[end])?a:(A[start]+A[end]);
        }
        int mid=(start+end)/2;
        int tmp_sum=A[mid];
        max_mid=tmp_sum;
       
        int i=mid-1;
        int j=mid+1;
        while(i>=start)  //難點在于當連續最大和子序列分布在mid的一側或兩側時，怎麼處理
        {
            
            tmp_sum+=A[i];
            i--;
            max_mid=max(max_mid,tmp_sum);
            
        }
        if(max_mid>A[mid])  //判斷是處于兩側，還是處于一側
            tmp_sum=max_mid;
        else
            tmp_sum=A[mid];
        while(j<=end)
        {
            
            tmp_sum+=A[j];
            j++;
            max_mid=max(max_mid,tmp_sum);
            
        }
        
        max_left=max(max_left,maxsub(A,start,mid-1));//二分輪廓
        max_right=max(max_right,maxsub(A,mid+1,end));
        int tmp_max = max(max_left,max_right);
        return max_mid>tmp_max?max_mid:tmp_max;
    }


};