[Java] 백준 연속합

1. 문제분석

 

테스트 케이스 1을 보면 단순히 연속되는 가장 큰수를 구하는 문제 같아보인다.

하지만 테스트 케이스 2는 음수를 가지고 있지만 가장 큰 수열에 속한다.

 

결국 여기서 포인트는 음수, 양수 상관없이 연속적인 수의 합이 최대값인 경우를 찾는 문제다.

따라서 점화식은 dp[n] = (dp[n-1] + arr[n], arr[n])의 최대값이다.
(전까지의 최댓값 + 현재값, or 지금 숫자가 최대값)

2. 구현

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());

        int[] arr = new int[size];
        int[] dp = new int[size];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for(int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        int max = arr[0];
        for (int i = 1; i < size; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

초기 dp값과 현재까지 최대값을 구해준다. 

arr[0]이 가장 큰 경우를 고려해 dp의 값을 구하고 현재 최대값과 dp값을 구해 결과를 출력하면 된다.

3. 마무리

간만에 알고리즘을 풀어보았다. 이번 dp문제는 쉬워서 금방할 수 있었다.