整形配列で、配列には正数も負数もあります.配列中の連続する1つ以上の整数は1つのサブ配列を構成し、各サブ配列には1つの和があり、すべてのサブ配列の和の最大値を求め、時間複雑度O(n)が要求される.

整形配列で、配列には正数も負数もあります.配列中の連続する1つ以上の整数は1つのサブ配列を構成し、各サブ配列には1つの和があり、すべてのサブ配列の和の最大値を求め、時間複雑度O(n)が要求される.
例えば、入力される配列が1,2,3,10,−4,7,2,−5の場合、最大のサブ配列は3,10,−4,7,2であるため、出力はこのサブ配列の和18である
本人はCC++レベルが限られているのでjava言語で実現します.
構想:配列の後ろから0未満または累積が0未満を排除し、除外されたサブ配列の和の最大値をmaxで記録する.

/***
 * @author lingxiasandu
 */
public class Test {

    public static void main(String[] args) {
        
        int[] a = {1, -2, 3, 10, -4, 7, 2, -5};
        int max = MaxSum(a);
        System.out.println(max);
    }
    
    /***
     * @param a    
     * @return           
     */
    public static int MaxSum(int[] a){
        int sum = 0;
        int max = 0;
        for(int i=0;i<a.length;i++){
            sum = sum + a[a.length-i-1];
            if(a[a.length-i-1] >= 0){
               if(max < sum){
                  max = sum ;
                }
            }
            if(sum < 0){
                 sum = 0;
             }
        }
        return max;
    }

}