[백준(Baekjoon)][자바(java)] 1912 : 연속합 / 동적 계획법 1

 

https://www.acmicpc.net/problem/1912

1912번: 연속합

 

< 풀이 방법 >

▶  길이가 n인 수열 A가 주어짐

▶  연속합을 구하는 작은 단위의 식 (누적)  ☞  A(i) = A(i-1) + A(i)  ( 0 < i < n )

                                                                                               이전 합   현재 항

▶  이전 합( A(i-1) )이 음수이고, 이전 합과 현재 항을 더한 값( A(i-1) + A(i) )이 음수면, 

     연속합을 구했을 때 수열의 현재 항( A(i) )보다 값이 작아지므로 이전 합을 더하지 않음

▶  1번째 항부터 n-1번째 항까지 반복하고 난 후, 수열 A에서의 최댓값이 연속합들의 가장 큰 합이 됨

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out) );
		
		int n = Integer.parseInt( br.readLine() ), i, max;
		int dp[] = new int[n];
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n; i++ ) 
			dp[i] = Integer.parseInt( st.nextToken() );

		max = dp[0];
		for( i = 1; i < n; i++ ) {
		    if( dp[i-1] > 0 && dp[i-1] + dp[i] > 0 ) 
		        dp[i] += dp[i-1];
		    if( max < dp[i] )
		        max = dp[i];
		}

		bw.write( max + "\n" );
		bw.flush();
		bw.close();
	}
}