[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 1912

주어진 수열에서 연속하는 수를 합쳤을 때의 최대값 구하기

 

- i개의 수를 가진 수열 a[], 인덱스 i까지의 수 중 a[i]와 연속한 수를 합한 최대값을 d[]에 저장함

- d[i]: a[i]와 연속한 수들의 합 중에서 최대값

- 즉, d[i]는 i-1까지의 연속한 수들의 합 중 최대값에서 a[i]를 더할지 말지 선택하여 나온 결과이다.

- d[]를 구한 뒤, 저장된 수 중 최대값을 고르면 정답.

 

import java.util.Scanner;

public class BOJ1912 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n + 1];
        int d[] = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            d[i] = a[i];
        }

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

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

    }
}