백준 1912 - Java

import java.util.Scanner;

public class ContinuousSum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //N입력받기
        int N=sc.nextInt();

        //arr입력받기
        int[] arr = new int[N];
        int[] dp = new int[N];
        for(int i=0;i<N;i++){
            arr[i]=sc.nextInt();
        }

        dp[0] = arr[0];
        int maxSum = arr[0];

        for (int i = 1; i < N; i++) {
            // dp[i]는 i번째 숫자를 마지막으로 하는 최대 연속 합
            dp[i] = Math.max(arr[i], dp[i - 1] + arr[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }

        System.out.println(maxSum);
    }
}

 

 

N= 10.. 

10

-4

3

1

5

6

-35

12

21

d-1

            6 

                               9 

                                                10..... 

    

이렇게 더하면서 가장 큰 값을 구하는 것이므로 동적계획법을 생각할 수 있다. 

따라서 위의 for 반복문을 사용한다면 아래와 같은 실행결과가 생긴다.

 

 

 

               i           arr[i]           dp[i-1]               dp[i-1] + arr[i]                   dp[i]            maxsum