kingsubin

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

public class boj_1912{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[] a;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        /** 깔끔한 점화식 풀이
         * for (int i = 1; i <= n; i++) {
         *             dp[i] = a[i];
         *             if (i == 0) continue;
         *             if (dp[i] < dp[i-1] + a[i]) {
         *                 dp[i] = dp[i-1] + a[i];
         *             }
         *         }
         */

        a = new int[n+1];
        dp = new int[n+1];

        int max = -1001;
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
            if (a[i] > max) {
                max = a[i];
            }
        }

        for (int i = 1; i <= n; i++) {
            if (dp[i-1] + a[i] > 0) {
                dp[i] = dp[i-1] + a[i];
            }
        }

        int ans = -1001;
        for (int i = 1; i <= n; i++) {
            if (dp[i] > ans) {
                ans = dp[i];
            }
        }

        // 음수일때
        if (ans == 0) ans = max;

        System.out.println(ans);
    }
}

 

- 점화식을 깔끔하게 세울 생각이 안나서 음수 양수로 구분해서 풀었다.

- 그냥 초기에 dp[i] = a[i]로 주면 음양 구분이 필요없다.

 

- 풀이할때 정리

1. 머릿속에서 먼저 풀이방법 생각

2. 그 다음에 코드 작성

3. 예시 전부 돌리고 다시 한 번더 생각