01-1. 最大子列和问题

题目链接：

该问题为最大子列和问题，所使用的解决方法是线性算法来解决

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

int maxSum ( int *arr , int len )
{
    int max , sub ;

    max = sub = 0 ;

    for ( int i = 0 ; i < len ; i++ )
    {
        sub += arr[i] ;
        if ( sub > max )
            max = sub ;
        if ( sub < 0 )
            sub = 0 ;
    }
        return max ;
}

int main ( void )
{
    int arr[100000] , K ;
    scanf ("%d" , &K ) ;

    for ( int i = 0 ; i < K ; i++ )
        scanf("%d" , &arr[i]) ;
    K = maxSum ( arr , K);
    printf ("%d" , K) ;

    system ("pause") ;
    return 0 ;
}

程序已经通过全部测试点

另外有一种通过递归的方法来实现的代码如下：

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


int maxOfThree ( int a , int b , int c )
{
    if ( a > b ) return a > c ? a : c ;
    else return b > c ? b : c ;
}

int maxSubSum ( int *arr , int from , int to )
{
    if ( from == to )
    {
        if ( arr[from] > 0 )
            return arr[from] ;
        else
            return 0 ;
    }

    int mid = (from+to) / 2 ;
    int leftMax = maxSubSum ( arr , from , mid ) ;
    int rightMax = maxSubSum ( arr , mid+1 , to ) ;

    // left border max
    int leftBorder = 0 , maxleftBorder = 0 ;

    // search from center to left <--- |center|
    for ( int i = mid ; i >= from ; i-- )
    {
        leftBorder += arr[i] ;
        if ( leftBorder > maxleftBorder )
            maxleftBorder = leftBorder ;
    }

    // right border max
    int rightBorder = 0 , maxrightBorder = 0 ;
    // search from center to right
    for ( int j = mid+1 ; j <= mid ; j++ )
    {
        rightBorder += arr[j] ;
        if ( rightBorder > maxrightBorder )
            maxrightBorder = rightBorder ;
    }

    return maxOfThree (leftMax , rightMax , (maxrightBorder+maxleftBorder)) ;
}

int main ( void )
{
    int arr[10000] , K ;
    scanf ("%d" , &K ) ;

    for ( int i = 0 ;i < K ; i++ )
    {
        scanf ("%d" , &arr[i]) ;
    }

    K = maxSubSum(arr , 0 , K-1 ) ;


    printf ("max sub sum = %d " , K ) ;
    system("pause") ;
    return 0 ;
}

此种方法稍加改进可以得到子序列在数列中的首尾坐标，时间复杂度为 O(NlogN)
前一种方法的时间复杂度为 O(N) ， 是一种在线处理算法。

如果需要求解的问题中不需要求取子序列在原数列中的起始结尾坐标的话，使用第一种方法最佳。
如果需要求解的问题需要求取子序列坐标，第一种方法无法求解，第二种实现方法最为适合。