백준 1912 연속합

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

public class SequenceSum {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N+1];
        for (int i = 1; i < N+1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        long[] dp = new long[N+1];
        dp[1] = arr[1];
        for (int i = 2; i < N+1; i++) {
            dp[i] = Math.max(dp[i-1] + arr[i],arr[i]);
        }


        long max = Integer.MIN_VALUE;
        for (int i = 1; i < N+1; i++) {
            max = Math.max(max,dp[i]);
        }
        System.out.println(max);
    }
}

풀이방법

📢이 풀이의 핵심은 dp배열에 처음 순열부터의 합, 현재값 둘중에 큰값을 메모이제이션 하는것이다.
이후 dp배열의 최댓값을 구하면 된다.

후기

나는 dp배열에 이후 순열의 합을 저장하고 접근했는데, 이런식의 접근에는 반례가 생겨서 풀 수가 없다.
dp배열에 어떤값을 메모이제이션 할지를 정하는것이 dp의 핵심인것 같다.