백준 1912번 : 연속합 java

이 문제는 다이나믹 프로그래밍 분야의 문제로 들어오는 값을 이전의 값들의 합이 최대 일 때와 비교해서 대입하면 됩니다.

예제 1번을 보면 처음에 10이 입력이 되는데 이때 비교할 이전 값이 없으니 intArr[0]번은 10입니다.

그 다음 -4의 값이 입력이 되는데 이전의 값이 10이고 10 + (-4) = 6으로 -4보다 6이 크니 intArr[1]번은 6이 됩니다.

3이 입력이 되면 3과 9(3+6) 중에서 9가 더 크므로 intArr[2]는 9가 됩니다.

이런 규칙으로 intArr[3] = 9+1, intArr[4] = 10 + 5, intArr[5] = 15 + 6, intArr[6] = 21 + (-35)이 대입됩니다.

intArr[6]에 -14가 들어있을 때 다음 입력값은 12입니다.

-14 + 12와 12를 비교하면 12가 더 크므로 intArr[7]에는 12가 들어갑니다.

intArr[8]에는 12 + 21이 들어가고 intArr[9]에는 33 + (-1)이 대입됩니다.

위의 알고리즘에 따라서 코드를 짜보았습니다.

---

import java.util.*;
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[] intArr = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++){
            int num = Integer.parseInt(st.nextToken());

            if(i == 0)
                intArr[i] = num;

            else{
                intArr[i] = Math.max(num, intArr[i-1] + num);
            }
        }

        int max = Integer.MIN_VALUE;
        for(int i = 0; i<N; i++)
            max = Math.max(max, intArr[i]);

        System.out.println(max);
    }
}

다이나믹 프로그래밍으로 풀 수 있다는 것만 알아챈다면 구현하기는 어렵지 않은 문제였습니다.