[백준(baekjoon) 1912] 연속 합

문제

백준 1912

n(1…100,000)과 n의 크기를 가진 수열이 주어질 때,
연속된 숫자들의 합 중 최대 값을 출력하라.

• 예시 : {10, -4, 3, 1, 5, 6, -35, 12, 21, -1}일 때, 12+21인 33이 정답이 된다.

해결

간단하게 앞에서 부터 시작해서 각 값으로 끝나는 연속된 수열의 최대 합을 구하면 된다.

1. 자신으로 시작하는 경우
2. 이전 연속 수열에 자신을 포함하는 경우

이렇게 두 가지의 경우로 나눌 수 있으므로, 두 값을 비교해서 큰 값을 저장하면 된다.
시간복잡도는 O(N)이다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

Top-down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[] input;
5.    static long max;
6.    public static void main(String[] args) {
7.        Scanner sc = new Scanner(System.in);
8.        int n = sc.nextInt();
9.
10.        input = new int[n + 1];
11.        for (int i = 1; i <= n; i++) input[i] = sc.nextInt();
12.        getMaxSum(n);
13.
14.        System.out.println(max);
15.    }
16.
17.    static long getMaxSum (int n) {
18.        if (n == 1) {
19.            max = input[n];
20.            return input[n];
21.        }
22.        long sum = Math.max(input[n], getMaxSum(n - 1) + input[n]);
23.        max = Math.max(max, sum);
24.        return sum;
25.    }
26.}

Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.
8.        long max = -1000000001;
9.        long[] dp = new long[n + 1];
10.        for (int i = 1; i <= n; i++) {
11.            int input = sc.nextInt();
12.            dp[i] = Math.max(input, dp[i - 1] + input);
13.            max = max < dp[i] ? dp[i] : max;
14.        }
15.        System.out.println(max);
16.    }
17.}

결과

1. Top-Down 방식
2. Bottom-Up 방식