백준알고리즘 1912번 연속합

문제링크

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

import java.util.Scanner;

//https://www.acmicpc.net/problem/1912
public class ConsecutiveSum {
    static int n;
    static int[] array;

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner scan = new Scanner(System.in);
        n = Integer.parseInt(scan.nextLine().trim());

        array = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = scan.nextInt();
        }

        System.out.println(consecutiveArrayCal());

    }

    static public int consecutiveArrayCal() {
        int maxData = array[0];

        for (int i = 0; i < array.length; i++) {
            int calData = 0;
            for (int j = i; j < array.length; j++) {

                calData += array[j];

                if (maxData < calData) {
                    int tmp = maxData;
                    maxData = calData;
                    calData = tmp;
                }
            }
        }
        return maxData;
    }

}

위의 예제는 for문을 2개 이용하여 정답을 구했지만 시간초과.... 배열이 길수록 n제곱이되니 시간초과가 된다.

다이나믹 프로그래밍 기법을 이용하여 메모이제이션을 이용한 아래 예제가 정답이 나왔다.

푸는데 진짜 오래걸렸다. 다이나믹 프로그래밍 문제가 제일 어려운듯 휴....

import java.util.Scanner;

//https://www.acmicpc.net/problem/1912
public class ConsecutiveSum {
    static int n;
    static int[] array;
    static int[] cache;

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner scan = new Scanner(System.in);
        n = Integer.parseInt(scan.nextLine().trim());

        array = new int[n];
        cache = new int[n];

        for (int i = 0; i < n; i++) {
            array[i] = scan.nextInt();
        }

        System.out.println(consecutiveArrayCal());
    }

    static public int consecutiveArrayCal() {
        cache[0] = array[0];
        int max = cache[0];
        for (int i = 1; i < array.length; i++) {
            cache[i] = Math.max(array[i], array[i] + cache[i - 1]);
            cache[i] = Math.max(array[i], cache[i]);

            if (max < cache[i])
                max = cache[i];
        }
        return max;
    }
}