[백준] 1912 - 연속합 (JAVA)

처음에는 '연속된 수의 합 중 가장 큰 값'을 찾는 문제니까 n 개가 연속된 합들을 구할 때 이전까지의 값을 활용(dp...)하고, 그렇게 구한 연속합 중 큰 값을 구하면 되겠다^^! 라고 생각했었다. 그러나 결과는 메모리 초과, 2차 시도는 시간 초과...
아래가 2차 시도 코드이다.

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        br.close();
        int max = -1001;
        int[] values = new int[n + 1];
        int[] sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            values[i + 1] = Integer.parseInt(tokenizer.nextToken());
            sums[i + 1] = values[i + 1];
            max = Math.max(max, values[i + 1]);
        }

        for (int i = 2; i < n + 1; i++) {
            for (int j = 1; j + i -1 <= n; j++) {
                sums[j] =  sums[j] + values[i+j-1];
                max = Math.max(max, sums[j]);
            }
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
    }

막연히 dp는 이전 값들을 배열에 저장해서 사용하는 것! 이라는 것에 꽂혀서 이런 생각을 했던 것 같다. 결국 다른 사람들의 풀이를 보고 아하.. 이전까지의 연속합의 자신의 값을 더한 값과 현재 자신의 값 중 큰 값을 취하는 거구나ㅠㅠ 깨닫고 다시 코드를 짰다.
아래가 그 코드이고 결과는 성공!
휴... dp 어렵다,,,

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

// 1912 - 연속합
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        br.close();

        int max = Integer.parseInt(tokenizer.nextToken());
        int sum = max;
        for (int i = 1; i < n; i++) {
            int input = Integer.parseInt(tokenizer.nextToken());
            sum = Math.max(input, sum + input);
            max = Math.max(sum, max);
        }

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
    }

}