近期学习了字符数组，偶尔看打一个求数组最大值的题，想了下。又上网搜搜了。。


字数组求最大值。


方法1：蛮力法 时间复杂度为O(N^2).
int MaxSum1(int *arr,int n)
{
    int sum = 0,max = INT_MIN;
    for(int i = 0; i<n; ++i)
    {
        sum = 0;
        for(int j = i;j<n; ++j)
        {
            sum += arr[j];
            if(sum>max)
                max = sum;
        }
    }
    return max;
}


方法2：这种方法网上很多，但是还是以编程之美上面提供的代码最为规范，它可以处理所有数都为负数和情况。大体思想，是如果子数组和为负数了，则抛弃现在在算的子数组，以下一个元素为头重新开始计算子数组之和，因为一个数与负数的和肯定会小于这个数本身。时间复杂度为： O(N)
int MaxSum2(int *A, int n)
{
    int nStart = A[n-1];
    int nAll = A[n-1];   
    for(int i = n-2;i>=0;--i)
    {
        if(nStart<0)
            nStart = 0;
        nStart += A;
        if(nStart>=nAll)
        {
            nAll = nStart;           
        }
    }
    return nAll;
}


方法3：分治法
设A为数组中的一个任意元素，则对于最大连续子数组和，有：
1、若最大子数组和中包括A这个元素，则从A往左找，找出左边的最大值，再从A往右找，找出右边的最大值，相加即得。
2、若最大子数组和中不包括A这个元素，则最大子数组和是A[0],...A[i-1]和A[i+1]...A[n-1]两个子数组最大和的最大值。
时间复杂度为O(NlgN)
int MaxSum3(int *A,int beg,int end)
{
    if(beg==end)
        return A[beg-1];
    int mid = (beg+end)/2;
    int left = MaxSum3(A,beg,mid);
    int right = MaxSum3(A,mid+1,end);
    int sum = A[mid-1];
    int i = mid-1, j = mid+1;
    int maxsum = A[mid-1];
    while(i>=beg)
    {
        sum+= A[i-1];
        if(sum>maxsum)
            maxsum = sum;
        --i;
    }
    sum = maxsum;
    while(j<=end)
    {
        sum+=A[j-1];
        if(sum>maxsum)
            maxsum = sum;
        ++j;
    }
    int max = left>right?left:right;
    max = max>maxsum?max:maxsum;
    return max;
}


注意：不考虑数组收尾相连。

学习了~~~