北大2479题

原题链接如下：

这道题，利用的方法是“求最大连续子段和”的方法。

核心思想是:

用数组A[N]记录所要求的数组，用数组B[N]来记录连续子段的和

可以知道：

初时值B[0] = A[0];

当B[K-1]>0时，，B[K]=B[K-1]+A[K]

当B[K-1]<0时，B[K]=A[K]

解题如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNUM 50100

long long    data[MAXNUM];
long long    left[MAXNUM];
long long    right[MAXNUM];

int    main()
{
    int    N, n;
    int    i, j;
    long    long max, prevalue;

    scanf( "%d", &N );  //N表示共有N组数组

    for( i=0; i<N; i++ )
    {
        scanf( "%d", &n );  //n表示每组数据的个数
        if( n > MAXNUM )
        {
            continue;
        }

        scanf( "%lld", &data[1] );
        left[1] = max = prevalue = data[1];

        for( j=2; j<=n; j++ )
        {
            scanf( "%lld", &data[j] );

            //按照求最大连续子段和的方法，求最大连续子段的和
            max_from_first_to_last( j, data[j], left, &prevalue, &max );
        }

        op_data( n );
    }

    return 0;
}

int    op_data( int n )
{
    long long    max = 0;
    int        i;

    max_from_last_to_first( n );
    //print_array( n, left );
    ////print_array( n, right );

    getmax( n );

    return 0;
}

int    print_array( int n, long long *a )
{
    int    i;
    for( i=1; i<=n; i++ )
    {
        printf( "%lld ", a[i] );
    }
    printf( "\n" );
}

/*
    从数组的左往右求最大连续子段的和

    int:            i - array index
    long long data        data[i]'s value
    long long *left:    it is a array
    long long *prevalue:    sum of data, which is from 1 to i-1
    long long *max
*/

int    max_from_first_to_last( int i, long long data, long long *left, long long *prevalue, long long *max )
{
    if( *prevalue > 0 )
    {
        *prevalue += data;
    }
    else
    {
        *prevalue = data;
    }

    if( *prevalue > *max )
    {
        *max = *prevalue;
    }

    left[i] = *max;

    return 0;
}
/*
从数组的右往左求最大连续子段的和
*/

int    max_from_last_to_first( int n )
{
    int    i = 0 ;
    long long    max, value;

    max = value = right[n] = data[n];

    for( i=n-1; i>=1; i-- )
    {
        if( value > 0 )
        {
            value += data[i];
        }
        else
        {
            value = data[i];
        }

        if( value > max )
        {
            max = value;
        }

        right[i] = max;
    }

    return 0;
}

int    getmax( n )
{
    int i;
    long long max, tmp;

    max = left[1] + right[2];
    for( i=2; i<n; i++ )
    {
        tmp = left[i]+right[i+1];
        if( tmp > max )
        {
            max = tmp;
        }
    }

    printf( "%lld\n", max );
}