[필수 문제] 연속 부분 최대합

1. 문제

N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.

---

입력

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다.

출력

연속된 부분을 선택하였을 때의 최댓값을 출력한다.

예제 입력

case 1)

8
2 3 -5 8 -3 4 2 -9

 

case 2)

5
-1 -2 3 -2 4

예제 출력

case 1) 11

case 2) 5

 

 

 

2. 풀이

이 문제의 풀이 방법은 굉장히 다양하다.

 

우선 완전 탐색의 방법으로 접근한다면, 모든 경우의 수를 시도하면 된다.

• 첫 번째 배열부터 시작하여 끝까지 하나씩 더하면서 최대값을 찾기
• 두 번째 배열부터 시작하여 끝까지 하나씩 더하면서 최대값을 찾기
• 세 번째 배열부터 시작하여 끝가지 하나씩 더하면서 최대값을 찾기
• 과정을 반복

 

하지만 완전 탐색으로 접근한다면, 시간 복잡도는 O(n^3)이 되기 때문에 이 방법으로는 접근해서는 안된다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

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

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int max = 0;
        for(int start = 0; start < n; start++) {
            for(int end = start; end < n; end++) {
                int sum = 0;

                for(int i = start; i <= end; i++) {
                    sum += arr[i];
                }

                if(max < sum) max = sum;
            }
        }
        bw.write(max + "");

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

}

그렇다면 시간복잡도를 줄이기 위한 방안으로는 무엇이 있을지 생각해보아야한다. 그 중 하나는 다음과 같다.

이 방법으로 접근할 경우에는 O(n^3)에서 O(n^2) 만큼의 시간복잡도로 줄일 수 있다.

package org.example;

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

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

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int[] sum = new int[n];
        sum[0] = arr[0];
        for(int i = 1; i < n; i++) {
            sum[i] = sum[i-1] + arr[i];
        }

        int max = 0;
        for(int start = 0; start < n; start++) {
            for(int end = start; end < n; end++) {

                int tmp = 0;
                if(start == 0) tmp = sum[end];
                else tmp = sum[end] - sum[start - 1];

                if(max < tmp) max = tmp;
            }
        }

        bw.write(max + "");
        br.close();
        bw.flush();
        bw.close();
    }

}

하지만 이 또한 n이 100,000일 경우 어마어마한 계산량이 필요하다. 이를 해결하기 위해서는 분할 정복법을 이용하면 된다.

 

우선 합병 정렬처럼 절반으로 문제를 나누고 각 케이스별로 나누어서 최대합을 찾아 해결하면 된다.

• 절반으로 나누었을 때 남은 왼쪽의 최대합
• 절반으로 나누었을 때 남은 오른쪽의 최대합
• 절반으로 나눈 지점을 기준으로 왼쪽의 최대값과 오른쪽의 최대값의 합
• 3개의 최대합 중 가장 큰 값이 정답

 

분할 정복법은 합병 정렬에서 사용한 방법과 동일한 방법을 이용하는 만큼 시간복잡도는 O(n logn)의 시간이 소요된다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int[] arr;

    public static void main(String[] args) throws IOException {

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

        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(getSeqMax(0, n-1) + "");

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

    private static int getSeqMax(int s, int e) {
        if(s == e) return arr[s];
        else {
            int mid = (s + e) / 2;
            int left = getSeqMax(s, mid); // 절반으로 나누었을 때 남은 왼쪽
            int right = getSeqMax(mid + 1, e); // 절반으로 나누었을 때 남은 오른쪽

            // 절반으로 나눈 기준에서 왼쪽 방향의 최대합
            int leftMax = -987987987;
            int leftSum = arr[mid];
            for(int i = mid - 1; i >= 0; i--) {
                leftSum += arr[i];

                if(leftMax < leftSum) leftMax = leftSum;
            }

            // 절반으로 나눈 기준에서 오른쪽 방향의 최대합
            int rightMax = -987987987;
            int rightSum = 0;
            for(int i = mid + 1; i <= e; i++) {
                rightSum += arr[i];

                if(rightMax < rightSum) rightMax = rightSum;
            }

            // 절반으로 나눈 기준의 최대합
            int midMax = leftMax + rightMax;
            
            return Math.max(Math.max(left, right), midMax);
        }
    }

}

여기서 한번 더 시간복잡도를 줄일 수 있는 방법을 생각해보면, 동적계획법을 이용한 방안이 있다.

배열에 기존값과 그 전까지 계산된 값 중 최대값을 저장하여 문제를 풀 수 있다. 이 방법의 시간복잡도는 각각의 값을 채우는데 더하는게 좋은지, 혼자 있는게 좋은지를 1번 비교하기 때문에 각각 O(1)의 시간을 소비한다. 이를 n번 수행하기 때문에 O(n)의 시간 복잡도를 가지게 된다.

 

즉, 완전 탐색과 분할 정복법보다 훨씬 코드가 간결해지고 빠르게 해결할 수 있음을 알 수 있다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int[] tmp;
    private static int[] arr;

    public static void main(String[] args) throws IOException {

        n = Integer.parseInt(br.readLine());

        tmp = new int[n];
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        tmp[0] = arr[0];

        int max = -987987987;
        for(int i = 1; i < n; i++) {
            tmp[i] = Math.max(tmp[i-1] + arr[i], arr[i]);
            if(max < tmp[i]) max = tmp[i];
        }

        bw.write(max + "");
        br.close();
        bw.flush();
        bw.close();
    }

}