[Algorithm Study] 백준 1912

문제 출처 : https://www.acmicpc.net/problem/1912

문제 정리

1. 수열의 길이 만큼에 해당하는 배열을 하나 만든다.
2. 배열의 각 위치에는 연속합에 대한 최대값을 저장한다.
3. 답은 배열에 저장된 값 중에 가장 큰 값을 반환한다.

위의 문제를 해결하기 위해서 bottum-up 방식을 이용했습니다. 이 문제를 해결하기 위한 아이디어는 전 단계에서의 연속합의 최대값 + 현재 위치의 값과 현재 위치의 값을 서로 비교해 큰 값을 저장하는 방식으로 문제를 해결해 나갔습니다.

소스 코드

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

import static java.lang.Math.max;


public 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());
        int[] num_arr = new int[n];
        int[] sum = new int[n];
        st = new StringTokenizer(br.readLine());

        for(int i = 0; i < n; i++){
            num_arr[i] = Integer.parseInt(st.nextToken());
        }
        sum[0] = num_arr[0];
        int answer = num_arr[0];
        for(int i = 1; i < n; i++){
            sum[i] = max(sum[i-1] + num_arr[i], num_arr[i]);
            answer = max(sum[i],answer);
        }
        System.out.println(answer);
    }

}