[알고리즘/C++] 부분 최대합 구하기

배열에서 연속된 부분의 합 중 최대값을 구하는 문제이다. 

 

 -1, 2, 4, -3, 5, 2, -5, 2 

 

이 중에서 최대 값은 

 

 -1, 2, 4, -3, 5, 2, -5, 2 

 

연속된 수의 합이 10으로 가장 크다. 

 

아래의 코드는 O(n^2)의 시간 복잡도로 최적해를 찾는 코드이다.

 

#include <bits/stdc++.h>
using namespace std;

int find_max_sum(int arr[], int n) {
	int best = 0;
	for (int a = 0; a < n; a++) {
		int sum = 0;
		for (int b = a; b < n; b++) {
			sum += arr[b];
			best = max(sum, best);
		}
	}
	return best;
}

int main() {
	int arr1[8] = { -1, 2, 4, -3, 5, 2, -5, 2 };
	cout << find_max_sum(arr1, sizeof arr1 / sizeof arr1[0]);
}

이를 O(n)의 시간 복잡도의 코드로 축약할 수 있다. 

 

int find_max_sum2(int arr[], int n) {
	int best = 0;
	int sum = 0;
	for (int k = 0; k < n; k++) {
		sum = max(arr[k], sum+arr[k]);
		best = max(best, sum);
	}
	return best;
}

 -1, 2, 4, -3, 5, 2, -5, 2 에서 첫번째 element인 -1을 건너뛰도록 한 이유는 무엇인가?

 

앞에서부터 순차적으로 더했을 때, -1 + 2 의 결과인 1보다, 그냥 2부터 시작하는게 더 큰 결과를 가져오기 때문이다. 

		sum = max(arr[k], sum+arr[k]);

따라서 k번째항까지의 합이 그냥 k번째항보다 작다면, sum은 k번째항 혼자로 업데이트된다. 

 

k번째 항부터 다시 합이 계산된다.