백준 | 1912번. 연속합 - DP 문풀

⬛ 백준 1912번. 연속합 - DP 문풀

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

1912번: 연속합

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

---

💚 문제 접근 방식

처음 풀 때, 어디부터 시작해서 N까지 고려하는 게 더 최선인지 매번 다르기 때문에 점화식 구하는 과정에서 꽤 헤맸다. 

• N번째 값으로 시작할 때와 N번째 값까지 더했을 때 중 더 큰 값을 dy[N]에 세팅하면 해결된다.
• dy[N] 점화식 : 1) 직전 합에 N을 마지막항으로 더한 합 2) N으로 시작하는 합 중에서 더 큰 값으로 세팅

풀이 설명

---

💚 제출 코드

import java.util.Scanner;

/**
 * 1912번. 연속합 - DP 문풀 
 * @author MYLG
 *
 */
public class Main {
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		int[] arr = new int[N+1];
		int[] dy =  new int[N+1];
		
		for(int i=1; i<=N; i++) arr[i] = kb.nextInt();
		
		dy[1] = Math.max(arr[1], dy[0] + arr[1]);
		for(int i=2; i<=N; i++) {
			//직전합에 현재값 더한 것(=N을 마지막으로 하는 합) vs N부터 시작하는 합 중 큰 값 세팅 
			dy[i] = Math.max(dy[i-1] + arr[i], arr[i]);
		}
		int max = Integer.MIN_VALUE;
		//dy[]에 담긴 값들 중 최대값
		for(int i=1; i<=N; i++) {
			max = Math.max(max, dy[i]);
		}
		
		System.out.println(max);
	}

}