AOJ:0022

gistfile1.java

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		while (true) {
			int n = scn.nextInt();
			if (n == 0) break;
			LinkedList<Integer> ls = new LinkedList<Integer>();
			int buf = 0;
			int max = -100000;
			for (int i = 0; i < n; i++) {
				int a = scn.nextInt();
				//与えられた数列の最大値maxを求める
				if (a > max) {
					max = a;
				}
				//同じ符号の連続した数値を足して配列に格納
				if ((buf + a) * (buf + a) >= buf * buf &&
						(buf + a) * (buf + a) >= a * a) {
					buf = buf + a;
				} else {
					ls.add(buf);
					buf = a;
				}
			}
			ls.add(buf);
			//与えられた数列の要素が全て0以下のとき、数列の最大値が最大部分列和
			if (ls.size() == 1 && ls.get(0) <= 0) {
				System.out.println(max);
				continue;
			}
			//配列の先頭が負なら除去
			if (ls.get(0) < 0) {
				ls.remove(0);
			}
			for (int i = 0; ls.size() >= 3; i++) {
				if (i == ls.size() - 2) break;
				// |a(i)| >= |a(i+1)| かつ |a(i+2)| >= |a(i+1)|のとき
				// a(i)、a(i+1)、a(i+2)をまとめる
				if (ls.get(i) * ls.get(i) >= ls.get(i+1) * ls.get(i+1) &&
						ls.get(i+2) * ls.get(i+2) >= ls.get(i+1) * ls.get(i+1)) {
					ls.set(i + 2, ls.get(i) + ls.get(i + 1) + ls.get(i + 2));
					ls.remove(i);
					ls.remove(i);
					i = -1;
				}
			}
			//残った配列の値の最大値が最大部分列和
			for (int i = 0; i < ls.size(); i++) {
				if (ls.get(i) > max) {
					max = ls.get(i);
				}
			}
			System.out.println(max);
		}
	}
}