[BOJ] 1912 연속합

연속합

풀이

• 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. -> dp 문제임
• dp[N] : N-1까지의 누적 최대합(dp[N-1]) + 현재 위치 값(arr[N]) vs 현재 위치 값(arr[N]) 을 비교해서 더 큰 수
  - dp 어려워서 죽어버릴거같다11!!!

코드

import java.util.*;
import java.io.*;
public class BOJ1912 {
    static int[] dp;
    static int[] arr;
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        dp = new int[N+1];
        for(int i=0;i<N;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int k=1;k<=N;k++){
            dp[k] = Math.max(dp[k-1]+arr[k-1],arr[k-1]);
        }

        int answer = Integer.MIN_VALUE;
        for(int i=1;i<=N;i++){
            answer = Math.max(dp[i],answer);
        }

        System.out.println(answer);
    }

}