[Java] 백준 1912 - 연속합

 

 

문제

풀이

임의의 수열이 주어지고 이중 한 개 이상의 연속된 수를 선택해 큰 수를 만드는 문제이다. 메모리제이션을 이용하면 어렵지 않게 풀 수 있다. 일반적으로 제일 큰수를 만든다고 생각하면 -가 붙은 수를 제외하여 더하겠지만 예제 2같은 경우에 3,4,-4,6,5 가 되어 14라는 제일 큰수를 만들수있다. 이경우 -4가 앞에 3,4를 더한 값보다 작기때문에 -4까지 더한 값이 큰값이되는것이다. 즉, 큰수는 음수 양수 상관없이 연속으로 선택한 값중 제일 큰 값를 찾으면 되는 것이다. 즉, 메모이제이션은 이전까지 탐색했던 값과 현재 위치의 값을 비교하여 큰 값을 저장하면 되는 것이다.

예제 입력2

 

 

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

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


    }
}