[백준][1912번] 연속합

문제 URL

https://www.acmicpc.net/problem/1912

나의 풀이

import java.io.*;
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 str = new StringTokenizer(br.readLine());
        int[] a = new int[n + 1];
        int[] d = new int[n + 1];

        for (int i = 1; i <= n; i++)
            a[i] = Integer.parseInt(str.nextToken());

        for (int i = 1; i <= n; i++) {
            int sum = d[i - 1] + a[i];
            if (sum > a[i]) {
                d[i] += sum;
            }else{
                d[i] = a[i];
            }
        }

        int max=-1001;
        for(int i=1; i<=n; i++){
            if(d[i] > max)
                max =d[i];
        }
        System.out.println(max);
    }
}

느낀점

동적계획법 을 이용한 문제다.

끝내 풀지 못하고 백준 강의를 통해 핵심개념을 파악하고 문제를 풀어봤다.

• D[i] = i번째 수로 끝나는 가장큰 연속합

두가지 케이스로 나눌수있다. i번째수가 i-1번쨰와 연속 또는 연속X 즉, D[i] = max(D[i-1] + A[i], A[i])