読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Maximum Sum Sequence(AOJ No.0022)

リポジトリ

Maximum Sum Sequence(AOJ No.0022)

 a_1 , a_2 , \cdots a_n が与えられたときの、最大の連続部分和を求める。
制約
 2\leq n \leq 5000
 -100000 \leq a_i \leq 100000

アルゴリズム

初期化 sum = a_1 , max = a_1
 2\leq i \leq nについて、
{ sum = \begin{cases} a_i && (sum + a_i < a_i ) \\ sum + a_i && (otherwise) \end{cases} }
で部分和を計算していって、毎回 max=\max \{sum,max\} で更新 O(n)

コード

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);
		}
	}
}