联机算法——最大子数组问题

代码

public class Max {
    private static int max ( int [] a ) {
        int sum = , thisSum = ;

        for ( int i = ; i < a.length-; i++ ) {
            thisSum += a[i];

            if ( thisSum > sum ) 
                sum = thisSum;
            else if ( thisSum <  )
                thisSum = ;
        }

        return sum;
    }

    //测试
    public static void main( String [] args) {
        int [] a = { , -, , -, -, , , -};
        System.out.println( max(a) );
    }
}
           

输出

11
           

简要分析

联机算法正确性不易看出，也难开发。

但仅需常量空间并以线性时间运算。