AOJ 0022 Maximum Sum Sequece

リンク AOJ 0022 Maximum Sum Sequece

方針

力ずくで解きました。全探索してO(n^2)です。
入力が1つだけの場合、入力が全て負の数の場合、この2つを忘れていて2WAくらいました・・・かなしい。

ちなみに、 AOJ 0022 とかで検索をかけると、もっと効率的な解法がありました。重ね重ね悲しいです。

ソース

import java.util.*;
public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static int[] input;
    public static void main(String[] args) {
        while(read()){
            solve();
        }
    }
    static boolean read(){
        n = sc.nextInt();
        if(n == 0)return false;

        input = new int[n];
        for(int i = 0; i < n; i++)input[i] = sc.nextInt();
        return true;
    }
    static void solve(){
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum = input[i];
            max = Math.max(sum, max);
            for(int j = i+1; j < n; j++){
                sum +=  input[j];
                max = Math.max(sum, max);
            }
            sum = 0;
        }
        if(n == 1){
            System.out.println(input[0]);
        }else{
            System.out.println(max);
        }
    }
}