문제 출처

단계별로 풀어보기 > 동적 계획법 1 > 연속합
https://www.acmicpc.net/problem/1912

문제 설명

n개의 정수로 이루어진 수열이 주어질 때, 연속된 몇 개의 수를 선택하여 구할 수 있는 합 중 가장 큰 합을 구하라.

접근 방법

dp[]를 만들어서, i번째는 i-1 값과 현재 값을 더했을 때와 arr의 i번째 값중 더 큰 값을 dp[i]에 저장한다. 이후, 기존까지 있었던 max 값과 dp[i]와 비교하여 더 큰 값을 max로 저장한다.

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

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

        int N = Integer.parseInt(br.readLine());

        int arr[] = new int[N];
        int dp[] = new int[N];

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

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

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

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

        bw.write(String.valueOf(max));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

연속합이 줄어들지 않는 경우는 해당 자리 수가 음수가 아닐 때를 가정하여 풀었었다. 그래서 dp[]에 현재 값과 이전 값을 넣어서 양수이거나 0일 경우, 그 값을 더하는 방식을 사용했었지만, 틀렸다.

코드의 시간 복잡도는 O(N) 이다.

문제푼 흔적