코드

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

class Main {
    static int N,max;
    static int[] arr;
    static int[][] memo;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        memo = new int[N][2];
        arr = new int[N];

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

        memo[0][0] = 0;
        memo[0][1] = arr[0];
        max = arr[0];
        for(int i=1; i<N; i++){
            memo[i][0] = Math.max(memo[i-1][0] + arr[i], memo[i-1][1]);
            memo[i][1] = Math.max(memo[i-1][1] + arr[i], arr[i]);
            max = Math.max(Math.max(memo[i][0], memo[i][1]),max);
        }

        System.out.println(max);
    }
}

• 그리디를 사용해서 풀이해보려다가 겁나게 틀렸다.
• DP의 점화식을 활용
  • 숫자 하나를 뺀 경우는 memo[i][1]에
  • 숫자를 빼지 않은 경우는 memo[i][0]에 저장한다.

        memo[i][0] = Math.max(memo[i-1][0] + arr[i], memo[i-1][1]);
        memo[i][1] = Math.max(memo[i-1][1] + arr[i], arr[i]);
        max = Math.max(Math.max(memo[i][0], memo[i][1]),max);

  • 항상 DP는 점화식 먼저 짜보는 것을 습관으로.