最大子序列和(連續)：，最大序列

最大子序列和(連續)：，最大序列

//最大子序列和(連續)：
//http://my.oschina.net/itblog/blog/267860

#include <iostream>  
using namespace std;

int MaxSum(int* a, int n)
{
    int sum = 0;
    int max = 0;

    //最大子序列第一個元素不可能是負數，
    //不可能包含和為0或負數的子序列作為前綴
    //這樣的話就避免了對同一個元素進行多次考慮
    for(int i=0; i<n; i++)
    {
        sum += a[i];
        if(sum > max )
            max = sum;
        else if(sum<0)
            sum=0;
    }
    return sum;

}

int main()  
{  

    int a[]={-1,-2,-3,-4};  //測試全是負數的用例  
    cout<<MaxSum(a,4)<<endl;
    int b[10]={1, -2, 3, 10, -4, 7, 2, -5};  
    cout<<MaxSum(b,8)<<endl;  
    system("pause");
    return 0;  
}  

/*
比如數組：1, -2, 3, 10, -4, 7, 2, -5
最大子序列和為13

一種是暴力枚舉O(n^3),兩個for循環確定邊界，第三個for循環遍歷相加比較。
    for(i=0,i---n) for(j=i,j---n) for(k=i,k---n) sum+=s[k]
一種遍歷O(n^2)：第二個for循環裡j一邊移動一邊相加然後比較。
    for(i=0,i---n) for(j=i,j---n) sum+=s[j]

一種是用DP來考慮，最大子序列要麼是在左半，要麼是在右半，要麼
橫跨左右O(nlogn)。
一種是線性的，如上O(n)
*/

//分治法：/要看看遞歸和二分了

#include <iostream>  
using namespace std;

//求三個數最大值 
int max3(int i, int j, int k)
{
    if (i>=j && i>=k)
        return i;
    return max3(j, k, i);
}

int maxsequence2(int a[], int l, int u)
{
    if (l > u) return 0;
    if (l == u) return a[l];

    int m = (l + u) / 2;

    //求橫跨左右的最大連續子序列左半部分
    int lmax=a[m], lsum=0;
    //這個循環是求這個序列的最大值，把所有元素相加
    for (int i=m; i>=l; i--) {
        lsum += a[i];
        if (lsum > lmax)
            lmax = lsum;
    }

    //求橫跨左右的最大連續子序列右半部分 
    int rmax=a[m+1], rsum = 0; 
    for (int i=m+1; i<=u; i++) { 
        rsum += a[i];
        if (rsum > rmax)
            rmax = rsum; 
    }
    //如果最大子序列跨越左半邊和右半邊的話，那麼就是左半邊的lmax和右半邊的rmax的和。

    return max3(lmax+rmax, maxsequence2(a, l, m), maxsequence2(a, m+1, u));
}

int main()  
{  
    //int a[]={-1,-2,-3,-4};  //測試全是負數的用例  
    //cout<<MaxSum(a,4)<<endl;
    int a[10]={1, -2, 3, 10, -4, 7, 2, -5};  
    cout<<maxsequence2(a, 0,8)<<endl;  
    system("pause");
    return 0;  
}