0x10 - DP : BOJ1912 연속합

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[] list = new int[n+1];
        //1. 테이블 설정
        // d[i] : list[i]번째 수를 탐색할 때 누적합의 최댓값
        int[] d = new int[n];

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

        //2. 초기값 설정
        d[0] = list[0];
        int max = d[0];
        //d[1] = Math.max(d[0]+list[1], list[1]);

        //3. 점화식
        // 다음숫자도 누적합 or 다음숫자로 새로 시작
        for (int i = 1; i < n; i++) {
            d[i] = Math.max(d[i - 1] + list[i], list[i]);
            max = Math.max(max, d[i]);
        }

        //4. 출력
        System.out.println(max);
    }
}

1. 테이블
   d[i] : list[i]번째 수를 탐색할 때 누적합의 최댓값

2. 초기값 설정
   d[0] = list[0];
   int max = d[0];
   맨처음 값과 최댓값 비교를 위한 max 설정

3. 점화식
   list[i]를 탐색하면서 d[i-1]+listi or list[i](다음숫자로 새로시작) 할 지 선택

한 번 작아지면 그 이후로도 더 커질 수 없기때문에 누적합 or 새로시작만 고민하면 됨

4. 출력
   처음엔 배열(=list[i]번째 수를 탐색할 때 누적합의 최댓값)을 다 채우고 마지막에 정렬해서 배열의 최댓값을 구했더니 다른 제출들에 비해 시간이 느리게 나와서,
   매 시도마다 max로 최댓값을 갱신해서 출력했다