[ALGORITHM] 최대 연속 부분 구간 합 문제를 푸는 4가지 방법

특정 배열에서, 특정 구간이 최대가 되는 구간의 합을 구하는 알고리즘을 푸는데는 4가지 방식이 있다.

일반적으로, 투포인터를 이용해 구간합을 구하는 방식이 흔하지만 4가지 방식을 각각 살펴보면서 큰 문제를 부분문제로 정의하는 방법에 대해 고민해보면 좋을것 같아 기록해두고 천천히 살펴보고 한다.

 

O(N^3)

int inefficientMaxSum(const vector<int>& A) {
	int N = A.size(), ret=MIN;
	
	for(int i=0; i<N; i++){
		for(int j=i; j<N; j++){
			int sum = 0;
			for(int k=i; k<=j; k++){
				sum += A[k];
			}
			ret = max(ret,sum);
		}
	}
	return ret;
}

O(N^2)

비효율적인 알고리즘 보다는 나은 알고리즘이고,
sum을 구하는 부분을 배열을 순회하는 동시에 max를 추출해 내는것으로 바꿈.

int betterMaxSum(const vector<int>& A){
	int N = A.size(), ret=MIN;
	for(int i=0; i<N; i++){
		int sum = 0;
		for(int j=i; j<N; j++){
			sum += A[j];
			ret = max(ret,sum);
		}
	}
	return ret;
}

O(NlogN)

O(NlogN)의 시간복잡도를 가진 알고리즘.
분할정복(재귀)를 이용해 부분합을 계산함.
배열을 중간지점을 기점으로 왼쪽 오른쪽으로 구분한 후에 각각의 부분합을 구함.
가장 큰 부분합이 왼쪽, 오른쪽 두 배열 사이에 걸쳐있다면 이 두 부분합을 더한다.
왼쪽, 오른쪽에서 부분합이 최대가 나오는 배열이 나온다면, 그것을 정답으로 출력한다.

int fastMaxSum(const vector<int>& A, int lo, int hi){
	if(lo == hi) return A[lo];
	
	int mid = (lo + hi)/2;
	int left = MIN, right = MIN, sum =0;
	for(int i=mid; i>= lo; i--){
		sum += A[i];
		left = max(left, sum);
	}
	
	sum = 0;
	
	for(int i=mid+1; i<=hi; i++){
		sum += A[i];
		right = max(right, sum);
	}
	
	int single = max(fastMaxSum(A,lo,mid), fastMaxSum(A,mid+1,hi));
	
	return max(left+right, single);
}

O(N)

부분합을 선형시간에 수행하는 알고리즘. 동적계획법을 이용함.
부분합의 성질상, A[i]번째 있는 원소를 마지막 원소로 가지는 알고리즘은
A[i-1]번째 원소를 포함하는 부분합 구간에서 A[i]를 더하면 됨.
그러나, A[i-1]번째까지의 부분합이 음수라서 A[i] 단독의 부분합이 최댓값이 되는 경우를 방지하기 위해
max(0,psum)을 해줌
이를 점화식으로 표현하면
maxAt(i) = max(0,maxAt(i-1)) + A[i]

int fastestMaxSum(const vector<int>& A){
	int N = A.size(), psum = 0, ret = MIN;
	for(int i=0; i<N; i++){
		psum = max(psum,0) + A[i];
		ret = max(ret,psum);
	}
	return ret;
}