[Baekjoon] 1912번 - 연속합(JAVA)

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

조건 체크

조건은 간단하다, 입력으로 주어진 n개의 정수중에서 연속된 수의 합 중 가장 큰 값을 고르면 된다.

예제에서는
10 -4 3 1 5 6 -35 12 21 -1 이 주어졌고,

이중에서 12 21을 더한 33이 가장 크다.

풀이

동적프로그래밍으로 문제를 접근하면 간단하게 풀 수 있는 문제이다.

주어진 입력을 저장하는 배열과, 합을 저장하는 배열만 존재하면 된다.

max 값으로 첫번째 인덱스 값을 저장하고 1번째 인덱스부터 for문을 통해 현재 인덱스와 이전 연속합중 큰 값을 해당 인덱스 연속합으로 저장하고,
해당 인덱스 연속합과 max값을 비교해 큰값을 max에 저장하면 된다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int[] arr = new int[N+1];
        int[] dp = new int[N+1];

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

        int maxVal = arr[1];

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

        bw.write(maxVal + "\n");

        bw.flush();
        bw.close();
    }
}