0022-Maximum Sum Sequence

問題（外部リンク）

Maximum Sum Sequence | Aizu Online Judge

実装の概要

iから始まる長さjの数列の和を一つ一つ計算して比較する方法が考えられますが、ループのやり方によってはO(N^3)となり間に合いません。
しかし、ループの回し方を工夫すればO(N^2)で済みます。ある場所から始まる長さjの配列の和を考えるとき、長さj-1までの結果にさらに値を足すようにすれば直前の結果をリサイクルできるからです。
なお、計算結果の格納にはlong型が必要になりますので注意してください。

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            int n = Integer.parseInt(br.readLine());

            if(n == 0){
                break;
            }

            long[] input = new long[n];
            for(int i = 0; i < n; i++){
                input[i] = Long.parseLong(br.readLine());
            }


            System.out.println(calcSumOfArray(input));
        }
    }

    static long calcSumOfArray(long[] input){
        int n = input.length;
        long maxSum = input[0];

        for(int i = 0 ; i < n ;i++){
            int sum = 0;

            for(int j = i; j < n; j++){
                sum += input[j];

                maxSum = Math.max(maxSum, sum);
            }
        }

        return maxSum;
    }
}