백준 1912 JAVA (연속합)

 

DP 파트라는 것을 인지하고 문제에 접근하면 생각보다 쉽게 풀 수 있는 문제입니다.

 

우선 임의의 수열에서 연속적인 합의 최댓값을 구한다는 것이 가장 중요한 특성입니다.

 

(1) 입력값이 한 개만 있을 경우 최댓값은 입력값 하나만 고려하면 됩니다.

 

(2)

입력값이 두 개인 경우 최댓값은 

arr[1]+arr[2]이 arr[2]보다 크면 됩니다.

이 결과를 dp[2]에 저장합니다.

arr[1] + arr[2]이 arr[2]보다 작으면 연속합이 배열 요소보다 작다는 것을 의미하기 때문에

앞의 값은 버리고 arr[2]를 dp[2]에 저장하여 2번부터 계산합니다.

 

이후는 (2)번의 반복입니다.

앞에서 구한 두번째 배열 dp[2]와 arr[3]을 비교하여

dp[2]+arr[3]이 arr[3]보다 크면 dp[3]에 dp[2]+arr[3]을 저장하고

아니면 arr[3]부터 연속합의 최댓값은 계산합니다.

 

 

<코드>

import java.io.*;
 
public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N + 1];
        String str[] = br.readLine().split(" ");
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(str[i - 1]);
        }
        br.close();
 
        int res = dp(arr, N);
 
        System.out.println(res);
    }
 
    private static int dp(int arr[], int N) {
        int dp[] = new int[N + 1];
 
        dp[1] = arr[1];
 
        if (N >= 2) {
            for (int i = 2; i <= N; i++) {
                if (arr[i] < arr[i] + dp[i - 1]) {
                    dp[i] = dp[i - 1] + arr[i];
                } else {
                    dp[i] = arr[i];
                }
            }
        }
 
        int max = Integer.MIN_VALUE;
 
        for (int i = 1; i < dp.length; i++) {
            max = Math.max(dp[i], max);
        }
 
        return max;
 
    }
}