백준 10211 - Maximum Subarray

https://www.acmicpc.net/problem/10211

10211번: Maximum Subarray

알고리즘 강의에서 배운 기억이 있는 문제.

브루트포스, 분할정복, 동적계획법 어떤 방식을 사용하느냐에 따라 시간복잡도가 O(N)에서 O(N^3)까지 천차만별이다.

 

dp를 적용해 푸는 방법을 알아보자. 분할정복은 좀 어렵다. (대충 설명하면 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로, 가운데에서 양쪽으로 이동하면서 합의 최대를 구하는데 이 때 분할정복을 이용해 배열을 반으로 잘라 계산을 반복하는 거임)

 

1) dp식 정의

dp[i] : i번째 원소까지 확인했을 때 maximum subarray의 합, 즉 부분 구간합의 최댓값

 

2) 초깃값

dp[1] = arr[1] (첫 번째 원소의 값)

만약 arr[1]이 음수라고 해도, 문제에서 아예 원소를 선택하지 않는 경우를 언급하지 않았으므로 dp[1]가 0이 될 수는 없다.

 

3) 점화식쭉 연결된 부분 구간을 설정하는 방식은 두 가지이다.

이전까지의 구간에 현재 값을 추가하거나, 현재 값부터 해서 새 구간을 시작하거나.

 

따라서 매 반복문마다 두 결과를 비교해, dp[i]에 더 큰 값을 저장한다.

dp[i] = max(dp[i-1] + arr[i], arr[i])

arr[i]가 선택되었을 경우 dp[i-1]은 음수일 것이고, 그러면 arr[i]에서 새로 시작하는 것이 더 큰 구간합을 가질 것이다.

 

애초에 dp[i-1]이 어떻게 음수냐? 하면4-1 -2 -3 4같은 입력에서는 원소를 아예 선택하지 않을(dp[i] = 0) 수는 없으므로 dp[1]부터 dp[3]까지 음수가 된다.

 

어쨌든 이렇게 합을 구하다 보면 dp[n]에는 부분 구간합의 최댓값이 저장될 것이고, 이를 출력하면 된다.

int MSS(vector<int>& v) {
	int size = v.size();
	int ret = v[0], sum = v[0];

	for (int i = 1; i < size; i++) {
		//이전 결과에서 계속 진행하는 경우, 현재 값에서 새로 시작하는 경우 중 최댓값
		sum = max(sum + v[i], v[i]);

		//매 계산마다 최댓값 저장
		ret = max(ret, sum);
	}

	return ret;
}

예전에 작성한 코드라 sum과 max를 썼는데, 여러분들은 dp 배열 방식을 사용해 풀어보자.