문제

BOJ 1912, 연속합

핵심

• 입력의 크기가 $10^5$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• n개의 정수로 이루어진 수열이 주어진다. 연속된 몇 개의 수를 선택해서 가장 큰 합을 구해야 한다. 최소 1개 이상 선택한다.
• 먼저 가장 큰 합을 구하기 위해 부분합을 저장해야 한다. 주어진 예시처럼 중간에 엄청 작은 음수가 있다면 이를 포함하면 부분합이 작아진다. 최대 부분합을 찾기 위해선 음수가 되는 부분은 무시하고 양수가 되는 합만을 저장해야 한다.

dp[i]: i - 1까지 더한 부분합 + i와 i 중 더 큰 수를 저장한다.

• 점화식에는 자연스럽게 그리디적인 풀이가 들어간다. 항상 큰 수만 저장하면 dp 배열에서 가장 큰 수가 연속된 수의 최대 합이기 때문이다. 위처럼 점화식을 세우게 되면 중간에 만나는 아주 작은 수와 음수만 존재하다가 매우 큰 수가 있는 경우를 효율적으로 해결할 수 있다.

개선

코드

시간복잡도

• $O(N)$

C++

#include <iostream>
#include <algorithm>
using namespace std;

int dp[100'004];
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int num;
		cin >> num;
		dp[i] = max(dp[i - 1] + num, num);
	}
	cout << *max_element(dp + 1, dp + n + 1);
}

Java

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[] dp = new int[100_004];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());
            dp[i] = Math.max(dp[i - 1] + num, num);
        }
        int mx = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i++) {
            if (dp[i] > mx)
                mx = dp[i];
        }
        System.out.println(mx);
        br.close();
    }
}