문제

문제 링크

이 문제는 배열의 연속합 중 가장 큰 값을 구하는 문제이다.

풀이

이 문제를 접근하는 방법은 두 가지입니다.

• 완전 탐색(시간 초과)
• 다이나믹 프로그래밍(통과)

완전 탐색(시간 초과)

먼저 완전 탐생으로 이 문제를 접근하면 다음과 같이 생각할 수 있습니다.
배열에서 구할 수 있는 모든 연속합을 구하는 것입니다. 이 방법은 배열을 두 번 반복하여 탐색하면 구할 수 있습니다.
하지만 이렇게 되면 시간 복잡도가 O(N^2)이 되기 때문에 N의 크기가 최대 100,000이기 때문에 시간 초과가 발생하게 됩니다.

다이나믹 프로그래밍(통과)

Idea

• 연속합은 자기 자신만 포함되어도 연속합이다.
• 이전까지의 최대 연속합이 이득이 되는지 확인.
  (순양에.. 이득이 됩니까..?)

즉, 자기 위치 기준 최대 연속합은 이전 연속합과 더하거나 더하지 않거나 2가지 중 한가지가 된다.

10은 기저사건으로 자기 자신이 최대 연속합이 됩니다.

이제 그 다음 -4에 대해서 보면, 이전 까지의 최대 연속합은 10입니다.
이전 최대 연속합(10)이 이득이 됩니까..? 네 됩니다.

이렇게 검사를 쭉 진행하다 보면 다음과 같이 표를 구성할 수 있습니다.

그리고 12 차례에서 다시 이전까지의 최대 연속합을 확인하면 -14입니다. 그렇지만 -14를 12에 더하면 자기 자신 혼자 있는 것보다 -14+12 = 2로 작아지게 됩니다. 따라서 12 차례에서는 이전까지의 최대 연속합을 더하지 않고 자기 혼자 독야 청청하게 됩니다.

이렇게 쭉 최대 연속합을 구하면 다음과 같이 됩니다.

여기서 최대 연속합 배열이 구하면 이 배열에서 최대값을 구하게 되면 정답을 구할 수 있게 됩니다!

최종적으로 정리하면 다음과 같습니다.

DP[i] : i번째 위치에서의 최대 연속합
기저 상태 : DP[0] = arr[0]

점화식은 이전의 연속합과 합하거나 하지 않거나 이므로 그 중 더 큰 값으로 구한다.
점화식 : DP[N] = Math.max(DP[N-1] + arr[N], arr[N])

자바

import java.io.*;
import java.util.Arrays;
import java.util.stream.Stream;

public class 백준_1912번_연속합 {

    static Integer[] arr;
    static int[] dp;

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

        String line[] = br.readLine().split(" ");
        arr = Stream.of(line).mapToInt(Integer::parseInt).boxed().toArray(Integer[]::new);

        dp[0] = Integer.parseInt(line[0]); //기저사건

        for(int i = 1; i < n; i++){
            dp[i] = (dp[i - 1] + arr[i]) > arr[i] ? dp[i - 1] + arr[i] : arr[i]; //점화식 구현
        }

        bw.write(String.valueOf(Arrays.stream(dp).max().getAsInt()));

        br.close();
        bw.flush();

    }

}

파이썬

n = int(input())
arr = list(map(int,input().split(' ')))

sum = [arr[0]]
for i in range(len(arr) - 1):
    sum.append(max(sum[i] + arr[i + 1], arr[i + 1]))
print(max(sum))