[백준] 1912: 연속합 JAVA

접근

dp[i]에는 i번째 자리까지 고려했을 때 가장 컸던 연속합을 저장하도록 한다. 따라서 연속적으로 수를 더해 나가다가 그 합이 되려 작아지는 경우에는 값을 재설정해줬다. 질문 게시판은 반례를 올려주시는 분들이 많아서 애용하는 편인데, 1912번 문제에 해당하는 반례를 모아서 작성해준 분이 계셔서 링크를 남긴다.
https://www.acmicpc.net/board/view/44227 

 

코드

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

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

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

        int sum = dp[0] = arr[0];

        for (int i = 1; i < n; i++) {
            sum = Math.max(sum + arr[i], arr[i]);
            dp[i] = Math.max(dp[i-1], sum);
        }

        System.out.println(dp[n-1]);
    }
}