求最大子数组和

#include <stdio.h>

#define MAXBETWEEN(a,b) ((a)>(b) ? (a):(b))
#define MIN_INT -65535

int maxSubSum(int a[], int len)
{
    int curSum=0, maxSum;
    int i;
    if(NULL == a || 0 == len)
        return -MIN_INT;

    maxSum = a[0]; // not

    for(i=0; i<len; ++i)
    {
        // if '+=a[i-1]' make curSum<0, curSum=a[i]
        if(curSum < 0)
            curSum = a[i];
        else
            curSum += a[i];
        if(maxSum < curSum)
            maxSum = curSum;
    }

    return maxSum;
}

// deprecated
int maxsum(int a[], int len)
{
    int cur, max, i;
    cur=max=a[0];
    for(i=1; i<len; ++i)
    {
        cur += a[i];
        if(cur > max)
            max = cur;
        else if(cur < 0)
            cur = 0; // not a[i] !!
    }
    return max;
}

/* 我们试着再观察这个数组的特点，一个元素一个元素的看。
*  根据A[0]是否在这个满足最大和的子数组中，我们可以分为两种情况。
* 1.       在。那么可以从A[0]开始求（比较容易）。
* 2.       不在。那么这种情况，又可以继续分为两种情况：A[1]在不在这个满足最大和的子数组中。
* 从这里我们可以观察出一种递归的特点，可以把一个规模为N的问题转化为规模为N-1的问题。
* 所以这个从A[0]到A[n-1]的最大和子数组问题分解成：
*   2.1    所求子数组中包含A[0]。如果不包含A[1]，则A[0]自己满足条件，此时Max（A[0]……A[n-1]）=A[0]。
*   如果包含A[1]，则Max（A[0]……A[n-1]）=A[0]+Max（A[1]……A[n-1]）。
*   2.2    所求子数组中不包含A[0]。Max（A[0]……A[n-1]）=Max（A[1]……A[n-1]）。
* 最后取以上三者的最大值即可
* 即Max（A[0]……A[n-1]）=max（ A[0], A[0]+Max（A[1]……A[n-1]）, Max（A[1]……A[n-1]））。
*/

 

// luisliu.blog.51cto.com/883990/227200
int maxSubSum2(int a[], int n)
{
    int i;
    int cur, max;

    if(NULL == a || 0 == n)
        return MIN_INT;

    cur = a[n-1];
    max = a[n-1];
    for(i=n-2; i>=0; --i)
    {
    // 要么最大和只包括a[i]自己，要么就是a[i]连上后面那个a[i+1]
        cur = MAXBETWEEN(a[i], a[i]+cur);
    // 最大和，要么是从i开始的，要么就还是从前的
        max = MAXBETWEEN(cur, max);
    }
    return max;
}

int selectMaxSubArr(int data[], int len, int *left, int *right)
{
    int sum, maxchild, i;
    sum = 0;
    maxchild = data[0];
    if(NULL == a || 0 == len)
        return MIN_INT;

    for(i=0; i < len; ++i)
    {
        if(sum < 0)
        {
            sum = data[i];
            *left = i;
        }
        else
        {
            sum += data[i];
        }

        if(maxchild < sum)
        {
            maxchild = sum;
            *right = i;
        }
    }
    if(maxchild < 0)
        *left = *right;

    return maxchild;
}

int main()
{
    int a[10] = {1, -2, 3, 10, -4, 7, 2, -5};
    // max sum of sub array is sum{3,10,-4,7,2} = 18.

    //int a[10] = {-2, -12, -3, -10, -4, -7, -1, -5};
    // max sum of sub array is -1.

    int left=0,right=0; //selectMaxSubArr
    //printf("max-sum of child array is: %d\n", maxSubSum2(a, 8));
    printf("max-sum is: %d\n", selectMaxSubArr(a, 8, &left, &right));
    printf("The max of sub array(0..n-1) is from %d to %d.\n", left, right);
}