/ BOJ

BOJ_1912_연속합_JAVA

문제 : 연속합

링크 : BOJ_1912_연속합

접근 방식

DP 문제이다. 이 문제는 어제 풀었던 포도주와 약간 비슷한 유형으로 느껴졌다.

수열이 주어질 때 연속된 숫자를 더한 합이 가장 큰 값을 구해야한다. 그 외의 제약조건은 없기 때문에 간단하게 생각해보자.

dp에 저장할 값의 조건과 예시는 다음과 같다.

지금까지의 최댓값이 현재 값보다 작으면 현재 값으로 덮어씌운다.

arr : 10 -4 3 1 5 6 -35 12 21 -1

dp : 10 6 9 10 15 21 -14 12 33 -1

얼핏 보면 값이 줄어드는데? 라고 생각할 수도 있다. 하지만 dp를 저장하는 과정에서, 가능한 값 중에 최댓값을 따로 저장함으로써 항상 최댓값을 구한 채로 있는 것이다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_1912_연속합 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));



		int N = Integer.parseInt(in.readLine());

		StringTokenizer st= new StringTokenizer(in.readLine()," ");
		int arr[] = new int[N];
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int dp[] = new int[N];

		dp[0] = arr[0];
		int ans = dp[0];
		for(int i=1;i<N;i++) {
			// dp 조건
		    // 지금까지의 최댓값이 현재 값보다 작으면 현재 값으로 덮어씌운다.
            // 10 -4 3 1 5 6 -35 12 21 -1
            // 10 6 9 10 15 21 -14 12 33 -1
			dp[i] = Math.max(arr[i], dp[i-1]+arr[i]);

			if(ans < dp[i]) {
				ans = dp[i];
			}
		}

		System.out.println(ans);

	}

}