[백준][C++] 10211: Maximum Subarray

문제 링크: https://www.acmicpc.net/problem/10211

 

유명한 문제죠. 최대 부분 배열 문제(Maximum subarray problem)인데요, 여러 풀이가 있습니다.

분할정복으로 푸는 방법은 저번 게시물에 올렸으니 이번에는 dp로 풀어보겠습니다.

 

dp[i] = 'i번째 원소로 끝나는 부분배열 합의 최대값'이라고 해봅시다.

dp[i]는 최대값을 반환하니까 dp[i-1]도 최대값을 반환할겁니다. 따라서 dp[i] = dp[i-1] + arr[i] 라고 하면 말이 되는 것 같습니다.

이때, dp[i-1]이 음수인 경우, 해당 구간은 포함하지 않고 arr[i]만 포함하는 것이 최선이 됩니다. 부분 배열이 되려면 최소한 원소 한 개 이상을 포함해야 하니 부분 배열 합의 값이 음수값이 될 수 있죠. 따라서 아래 식처럼 쓸 수 있습니다.

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

배열을 만들 필요는 없고, 변수 하나에 계속 누적해서 누적합(prefix sum)을 만들어주고 최대값 변수 하나 만들어서 max값을 찾으면 됩니다.

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> v(n);
		for (auto& c : v)
			cin >> c;

		int max_val = -1e9;
		int psum = 0;
		for (int i = 0; i < n; ++i) {
			psum = max(0, psum) + v[i];
			max_val = max(max_val, psum);
		}
		cout << max_val << '\n';
	}

	return 0;
}