Maximum Sum Sequence(AOJ No.0022)

リポジトリ

Maximum Sum Sequence(AOJ No.0022)

• contiguous

が与えられたときの、最大の連続部分和を求める。
制約

アルゴリズム

初期化
について、

で部分和を計算していって、毎回で更新。

コード

import java.util.*;
public class aoj0022 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		while(true){
			int n = stdin.nextInt();
			if( n == 0 ) break;
			int sum = stdin.nextInt(), max = sum;
			for(int i=1; i < n ; ++i){
				int x = stdin.nextInt();
				sum = sum + x < x ? x : sum + x;
				max = Math.max(sum, max);
			}
			System.out.println(max);
		}
	}
}