[알고리즘] 백준 1912 - 연속합

분류 : DP

1. 문제

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

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

2. 입력

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

3. 풀이

1) 문제 쪼개기

원래 문제 : 전체 배열에서 연속된 숫자를 선택해서 가장 큰 합을 만들기
쪼갠 문제 : 현재 위치까지 연속된 숫자를 선택해서 가장 큰 합을 만들기

2) 점화식 구하기

(arr : 입력 인자 배열)

Dy[0] = arr[0]
Dy[1] = max(a[1], a[0]+a[1])
(현재까지의 연속합과 현재 입력 인자 배열 값 중 큰 쪽을 선택)

-> 여기서 점화식을 도출하면

Dy[i] = max(arr[i], Dy[i-1]+arr[i])

3) 점화식 이용

배열 끝까지 연산이 끝나면, Dy 배열에는 i시점까지 가장 큰 연속합들이 저장되어 있다.
그 중 가장 큰 연속합이 정답이다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class continue_sum_1912 {

    static int[] arr;
    static int[] sum_arr;

    public static void solution() throws IOException{
        BufferedReader bf= new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bf.readLine());

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

        //입력 숫자 배열
        arr = new int[n];

        //DP 배열(최대 합 저장)
        sum_arr = new int[n];

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


        //DP 연산
        sum();

        //DP 연산으로 저장된 예비 최대합들 정렬
        Arrays.sort(sum_arr);

        //최대합 출력
        System.out.println(sum_arr[n-1]);
    }

    public static void sum(){

        sum_arr[0] = arr[0];

        for(int i=1;i<arr.length;i++){
            //Dy[i+1] = Max(arr[i+1], Dy[i]+arr[i+1])
            //Dy[0] = arr[0]
            //이전까지 최대합 값과 현재 입력 배열 값 중 큰 쪽 선택
            sum_arr[i] = Math.max(arr[i], sum_arr[i-1]+arr[i]);
        }

    }



}