算法导论3：最大子数组问题 2016.1.3

顶着期末复习的压力，还是在今天过完之前看完了一个算法——最大子数组问题。

《算法导论》中引入这个问题是通过股票的购买与出售，经过问题转换（转换的过程比较简单，但是不好想），将前一天的当天的股票差价重新表示出来，即转为了一个最大子数组的问题，具体内容是：
13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 找到这连续的16个数里面的连续和最大的子数组;
书中差不多是这个意思：假定我们要寻找子数组A[low..high]的最大子数组，使用分治法意味着我们要将子数组划分为两个规模尽可能相等的子数组。也就是说，找到子数组的中央位置，比如mid，然后求解两个子数组A[low..mid]和A[mid + 1..high]。所以，A[low..high]的任何连续子数组A[i..j]所处的位置必然是三种情况之一： 1.完全位于子数组A[low..mid]中，因此low<=i<=j<=mid; 2.完全位于子数组A[mid + 1..high]中，因此mid<=i<=j<=high; 3.跨越了中点，因此low<=i<=mid<J<=HIGH;< strong=""></J<=HIGH;<> 因此，A[low..high]的一个最大子数组所处的位置必然是这三种情况之一。实际上，A[low..high]的一个最大子数组必然是完全位于A[low..mid]中、完全位于A[mid + 1..high]中或者跨越中点的所有子数组中和最大者。

参看原问题的话可以看一下这个博客（大神写的比我好多啦QAQ）：http://www.cnblogs.com/sungoshawk/p/3632408.html

所以又是一个二分的递归，复杂度nlgn。（看了网上有一些动态规划n复杂度的以后有空在学学）

根据这个分治法的话，如果我想知道整个数组的最大子数组，只需要知道前半部分的最大子数组，后半部分的最大子数组，还有跨越中间的最大子数组。

怎么知道前半部分的最大子数组？递归。

怎么知道后半部分的最大子数组？递归。

怎么知道跨越中间的最大子数组？有一个线性复杂度的算法。因为有限制，必须跨越中间。所以假定做一个函数

int maxcrossarray(int *a,int l,int mid,int r,int *ll,int *rr); //用来找跨越mid的最大子数组

只需要从mid向左找，记录下最大值k1,从mid向右找，记录下最大值k2,返回k1+k2即可。int *ll,int *rr是用来记录路径的。

这样就递归的把问题解决了。

下面是代码：

#include<stdio.h>

int maxcrossarray(int *a,int l,int mid,int r,int *ll,int *rr)
{
    int lmax=-100000;
    int i,li,ri;
    int sum=0;
    for (i=mid;i>=l;i--) {
        sum+=a[i];
        if (sum>lmax) {
            lmax=sum;
            li=i;
        }
    }
    sum=0;
    int rmax=-100000;
    for (i=mid+1;i<=r;i++) {
        sum+=a[i];
        if (sum>rmax) {
            rmax=sum;
            ri=i;
        }
    }
    *ll=li;
    *rr=ri;
    return (lmax+rmax);
}

int maxsonarray(int *a,int l,int r,int *ll,int *rr)
{
    if (l==r) {
        *ll=l;
        *rr=r;
        return a[l];
    }
    else {
        int mid=(l+r)/2;
        int k1=maxsonarray(a,l,mid,ll,rr);
        int l1=*ll,r1=*rr;
        int k2=maxsonarray(a,mid+1,r,ll,rr);
        int l2=*ll,r2=*rr;
        int k3=maxcrossarray(a,l,mid,r,ll,rr);
        int l3=*ll,r3=*rr;
        if (k1>k2 && k1>k3) {
            *ll=l1;
            *rr=r1;
            return k1;
        }
        if (k2>k1 && k2>k3) {
            *ll=l2;
            *rr=r2;
            return k2;
        }
        *ll=l3;
        *rr=r3;
        return k3;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int i;
    int a[15]={};
    for (i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    int l,r;
    int ans=maxsonarray(a,1,n,&l,&r);
    printf("%d
%d %d",ans,l,r);
    return 0;
}

说实话这个代码是照搬伪代码，细节上还不够严谨，还有待修改。