[백준] 1912 연속합_Java

📖  문제

---

백준 1912

⚠️  주의사항

---

• 중간에 음수가 들어갈지라도 최댓값이 될 수도 있다.

0	1	2	3	4	5	6	7	8	9
2	1	-4	3	4	-4	6	5	-5	1

위 표에서 최댓값은 index 3~7사이의 합이다.

 

즉 음수 양수 상관없이 생각해야한다.

✍️  이해

---

/**
 * 1. dp 식 찾기
 *  dp[i] = Math.max(dp[i-1] + arr[i], arr[i])
 * 2. 즉 이전까지의 합 + 현재 arr을 더한것과 / 현재 arr만 비교 해서 더 높은 것을 dp에 저장
 * 3. max에 현재 dp값과 max값 비교
 */

 

✏️  풀이

---

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

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 + 1];
        int[] dp = new int[N + 1];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 1; i <= N; i++) arr[i] = Integer.parseInt(st.nextToken());

        dp[1] = arr[1];
        int max = arr[1];

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

            max = Math.max(max, dp[i]);
        }
        System.out.println(max);
    }
}

---