백준 - 연속합 1912 java

---

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

1912번: 연속합

---

[문제 접근]

• input으로 주어진 값이 너무 커서 완전 탐색으로 접근하게되면 시간 복잡도가 어마어마 해질거 같았습니다.
• 그래서 dp 메모제이션으로 문제 접근을 해봤습니다.
• 우선 저는 연속된 수를 골랐을 때, 연속된 수를 고르지 않았을 때 두 가지 경우로 나누어서 생각했는데요
• dp[i] 배열에는 i번째 수에서 최대로 만들 수 있는 값을 저장하면 점화식은 아래와 같아집니다.
• dp[i] = Math.max(dp[i]-1 + arr[i], arr[i])
• dp[i-1]  + arr[i]는 연속된 수를 골랐을 때, arr[i]는 연속된 수를 고르지 않았을 때 입니다.
• 이렇게 각 i번째 dp 배열에는 최대로 만들 수 있는 값을 저장하고 dp배열에 갱신된 최대 값을 출력해주면 됩니다.

---

[java]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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());
        int arr[] = new int[n];
        int dp[] = new int[n];

        String input[] = br.readLine().split(" ");
        for(int i=0; i<input.length; i++) arr[i] = Integer.parseInt(input[i]);

        dp[0] = arr[0];

        int ans = dp[0];
        for(int i=1; i<n; i++){
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
            ans = Math.max(ans, dp[i]);
        }

        System.out.println(ans);

    }
}