[백준 1912] - 연속합 자바(JAVA)

[문제]

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

1912번: 연속합

---

[문제 풀이]

• 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하기.

주의해야 할 점은 음수를 제외한 연속합이 최대이지 않을까라고 생각을 할 수 있는데 음수를 포함해도 연속합이 커지는 경우가 있다. 

ex) 3 -1 3   최대합 : 5

 

문제를 참고하여  D[i] = i 번째 수로 끝나는 가장 큰 연속합이라는 점화식을 세울 수 있다.

 

			A[i]
		A[i-1]	A[i]
	A[i-2]	A[i-1]	A[i]
A[i-3]	A[i-2]	A[i-1]	A[i]

1. 새로운 연속합이 시작한 경우 A [i]

2. A [i-1]로 끝나는 가장 큰 연속합 뒤에 + A [i]가 추가된 경우

 

D [i] = Max( D [i-1] + A [i] , A[i] )

 

위의 점화식을 이용하여 예제 입력을 대입하면 아래와 같은 결과가 나온다.

 

 

i	1	2	3	4	5	6	7	8	9	10
A[i]	10	-4	3	1	5	6	-35	12	21	-1
D[i]	10	6	9	10	15	21	-14	12	33	32

• 문제의 답은 D [N] 이 아닌 D[1] ~ D[N] 중에서 가장 큰 값이다.

---

[코드]

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

public class boj1912 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int a[] = new int[n];
		int d[] = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		d[0] = a[0];
		for(int i=1; i<n; i++) {
			if(d[i-1] + a[i] < a[i]) {
				d[i] = a[i];
			}else {
				d[i] = d[i-1] + a[i];
			}
		}
	
		int ans = -1001;
		
		for(int i=0; i<n; i++) {
			if(ans < d[i]) ans = d[i];
		}
		
		System.out.println(ans);
	}
}

 

궁금하신 점이나 오류가 있을 경우 댓글로 남겨주시면 감사하겠습니다.