[종만북] 최대 연속 부분 구간 합 문제 - 브루트포스(BruteForce) + 분할 정복(DivideAndConquer) + 동적계획법(DynamicProgramming) JAVA

출처 4.6 수행 시간 어림짐작하기 - 실제 적용해보기 (종만북)

코드설명

널리 알려진 문제입니다.

주어진 배열이 존재할떄, 최대 합을 갖는 부분 구간을 구합니다.

 

입력 예시 1

8
-7 4 -3 6 3 -8 3 4

 

결과 예시 1

[4, -3, 6, 3] 이 최대 부분 구간 합입니다.

10

 

코드

첫번쨰 방법입니다. 무작정 2중 for문을 사용한다면 너무 쉽게 구할 수 있으므로 넘어갑니다. 2중 for문으로 구하면 O(N^2)으로 구할 수 있습니다. 일종의 누적합 혹은 투포인터라고 생각하시면 됩니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int[] A = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(partialSum(A));
	}
	
	public static int partialSum(int[] A) {
		int ret = Integer.MIN_VALUE;
		for(int i=0;i<A.length;i++) {
			int partialSum = 0;
			for(int j = i; j<A.length;j++) {
				partialSum += A[j];
				ret = Math.max(ret, partialSum);
			}
		}
		return ret;
	}
	
}

이 방법보다 더 안좋은 방법도 존재합니다. 만약 첫번쨰 방법과 다르게 모든 구간을 새로 연산한다면, O(N^3)이 됩니다. 

 

두번쨰 방법입니다. 분할정복 기법을 활용합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int[] A = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(getMaxSumByDivideAndConquer(A, 0, A.length - 1));
	}
 
	//최대 연속부분 구간 합 문제를 푸는 분할 정복 알고리즘
	// A[lo..hi]의 연속된 부분 구간의 최대합을 구합니다. 시간복잡도는 O(nlogn)
	public static int getMaxSumByDivideAndConquer(int[] A, int lo, int hi) {
		//기저사례 : 구간의 길이가 1 일 경우
		if(lo == hi) return 1;
		
		//배열을 A[lo..mid], A[mid + 1 ..hi] 의 두 조각으로 나눈다.
		int mid = (lo + hi) / 2;
		
		//두 부분에 모두 걸쳐있는 최대합 구간을 찾는다.
		//이 구간은 A[i..mid]와 A[mid+1..j] 형태를 갖는 구간의 합으로 이루어진다.
		//A[i..mid] 형태를 갖는 최대 구간을 찾는다.
		int left = Integer.MIN_VALUE, right = Integer.MIN_VALUE, sum = 0;
		for(int i=mid; i>=lo; i--) {
			sum += A[i];
			left = Math.max(left, sum);
		}
 
		//A[mid+1..j] 형태를 갖는 최대 구간을 찾는다.
		sum = 0;
		for(int j=mid+1; j<=hi; j++) {
			sum += A[j];
			right = Math.max(right, sum);
		}
		
		//최대 구간이 두 조각 중 하나에만 속해있는 경우의 답을 재귀호출로 찾는다.
		int single = Math.max(getMaxSumByDivideAndConquer(A, lo, mid), getMaxSumByDivideAndConquer(A, mid+1, hi));
		
		//두 경우 중 최대치를 반환한다.
		return Math.max(left + right, single);
	}
	
}

 

세번째는, 점화식을 이용합니다.

getMaxSum(i) = Math.max(getMaxSum(i - 1), 0) + A[i];

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		int[] A = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			A[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(getMaxSum(A));
		
	}
	
	
	public static int getMaxSum(int[] A) {
		int tempSum = 0;
		int ret = 0;
		for(int i=0;i<N;i++) {
			tempSum = Math.max(tempSum, 0) + A[i];
			ret = Math.max(ret, tempSum);
		}
		return ret;
	}
}