【编程珠玑】第八章：算法设计技术

一，概述
       问题：求一维数组中连续子向量的最大和。
       例如：a[6]={3,4,-2,-9,10,8}; 则最大连续子向量的和为 10+8 = 18
       1）解法一：简单算法
[html] #include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int main()
{
    int a[6]={3,4,-2,-9,10,8};
    int i,j,k;
    int sum=0;
    int maxsofar=0;


    for(i=0;i<6;++i)
    {
        for(j=i;j<6;++j)
        {
            sum=0;
            for(k=i;k<=j;++k)
            {
                sum+=a[k];
            }
            maxsofar=max(maxsofar,sum);
        }
    }

    printf("max=%d\n",maxsofar);
    return 0;
}
       2）两个平方算法
             算法一：
[html]
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int main()
{
    int a[6]={3,4,-2,-9,10,8};
    int i,j;
    int sum=0;
    int maxsofar=0;


    for(i=0;i<6;++i)
    {
        sum=0;
        for(j=i;j<6;++j)
        {

            sum+=a[j];
            maxsofar=max(maxsofar,sum);
        }
    }

    printf("max=%d\n",maxsofar);
    return 0;
}

              算法二：
[html]
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int main()
{
    int a[6]={3,4,-2,-9,10,8};
    int cumarr[6]; cumarr[-1]=0;
    int i,j;
    int sum=0;
    int maxsofar=0;

    for(i=0;i<6;++i)
    {
        cumarr[i] = cumarr[i-1] + a[i];
    }
    for(i=0;i<6;++i)
    {
        sum=0;
        for(j=i;j<6;++j)
        {

            sum = cumarr[j] - cumarr [i-1];
            maxsofar=max(maxsofar,sum);
        }
    }

    printf("max=%d\n",maxsofar);
    return 0;
}

            3）分治算法
思想：以m为分界线，最大值有三种情况
            一：在m左侧
            二：在m右侧
            三：跨越m
关键：最初求解左右最大值时候，一定要从中间向两侧递增。看源码解释……
[html]
#include "stdio.h"
#define max(a,b) a>b?a:b

int a[6]={3,4,-2,-9,10,8};
int max2(int a,int b,int c)
{
    if(a>b&&a>c)
        return a;
    else if(b>a&&b>c)
        return b;
    else return c;
}
int maxsum(int l,int u)
{
    int i,m,sum,lmax,rmax;
    if(l>u)
        return 0;
    if(l==u)
        return max(0,a[l]);
        m=(l+u)/2;

    lmax = sum =0;
    for(i=m;i>=l;--i)
    {
        sum += a[i];
        lmax =max(lmax,sum);
    }

    printf("m=:%d\n",m);
    rmax =sum =0;
    for(i=m+1;i<=u;++i)
    {
        sum += a[i];
        rmax =max(rmax,sum);
    }
    return max2(lmax + rmax , maxsum(l,m) , maxsum(m+1,u) );
}
int main()
{
    int maxsofar=maxsum(0,5);
    printf("max=%d",maxsofar);
    return 0;
}

【注意】 max2() 如果用宏 #define max(a,b,c)    max(a,b) >c?max(a,b):c 则不会得到正确结果

           4）扫描算法 www.zzzyk.com
[html]
#include "stdio.h"
int main()
{
    int a[6]={3,4,-2,-9,10,8};
    int i,sum=0;
    for(i=0;i<6;++i)
    {
        sum+=a[i];
        if(sum<0)
            sum=0;
    }

    printf("ma

补充：软件开发 , 其他 ,