다이나믹 프로그래밍_1912 : 연속합 JAVA

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

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

예제 출력 1 복사

33

예제 입력 2 복사

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2 복사

14

예제 입력 3 복사

5
-1 -2 -3 -4 -5

예제 출력 3 복사

-1

 

첫번째 예시는 다음과 같습니다.

두번째 예시는 다음과 같습니다.

두번째 예시를 보면 중간에 index 5가 음수이지만, index 7까지 합한 것이 최대값임을 알 수 있습니다. 즉 음수와 상관없이 연속적으로 선택한 수의 합 최대값을 찾으면 됩니다.

 

예시와 dp값을 비교하면 다음과 같습니다

 

예시 1

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

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

 

예시 2

arr : 2 1 -4 3 4 -4 6 5 -5 1

dp :  2 3 -1 3 7 3 9 14 9 10

 

dp를 구하기 위한 점화식은 다음과 같습니다.

dp[i] = Math.max(dp[i-1]+arr[i],arr[i]); // 그동안 더한값에 현재 값을 더한 값과 현재 값을 비교하여 큰 값이 dp[i]에 들어갑니다

 

점화식을 바탕으로 구현한 방식은 다음과 같습니다.

StringBuilder와 Buttom-up 방식을 이용하였습니다.

 

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

class Main{
	public static void main(String[] args){
    	StringBuilder sb = new StringBuilder(new InputStreamReader(System.in));
        int N = Integer.parseInt(sb.readLine());
        
        int[] arr = new int[N];
        int[] dp = new int[N];
        
        StringTokenizer st = new StringTokenzier(br.readLine()," ");
        
        for(int i=0;i<N;i++){
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        dp[0] = arr[0];
        int max = dp[o];
        
        for(int i=1;i<N;i++){
        	dp[i] = Math.max(dp[i-1]+arr[i],arr[i]);
            max = Math.max(max,dp[i]);
        }
        System.out.print(max);
    }
}