[Java][1912] 연속합

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

1912번: 연속합

코드:

import java.util.*;

public class Main {
    public static int n;
    public static int [] arr = new int[100005];
    public static int [] dp = new int[100005];
    public static void run(){
        for(int i=1;i<n;i++){
            dp[i] = Math.max(dp[i-1]+arr[i] , arr[i]);
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        dp[0] = arr[0];

        run();

        int maxval = Integer.MIN_VALUE;
        for(int i=0;i<n;i++){
            maxval = Math.max(maxval, dp[i]);
        }

        System.out.println(maxval);
    }
}

 

초기값
dp[0] = arr[0]

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

점화식
dp[i] = Math.max(dp[i-1]+arr[i] , arr[i]);

dp[i] 는 dp[i-1]+arr[i]와 arr[i] 중 최대값

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

예시
10 -4 3 1 5 6 -35 12 21 -1

dp[i]
10 6 9 10 15 21 -14 12 33 32

dp[6](-35) 까지는 계속 연속해서 더한 값이 최대가 되지만
dp[7]에선 (dp[6]+arr[7] = 2) < (arr[7] = 12) 이기 때문에
dp[7] = arr[7]이 된다.