AOJ 0022 Maximum Sum Sequece
リンク AOJ 0022 Maximum Sum Sequece
方針
力ずくで解きました。全探索してです。
入力が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); } } }