BOJ 10211 C++

문제접근

구간합 알고리즘을 이용하여 풀 수 있다.

pre[i] = max(pre[i - 1] + x[i - 1],x[i - 1]);

지금까지의 합이 배열 x의 인덱스 보다 작으면 pre[i] = x[i - 1];
아니면 계속해서 누적합.

코드

#include <bits/stdc++.h> 
#define ll long long
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> x(n);
		vector<int> pre(n + 1,0);
		int ans = -999;
		for (int i = 0; i < n; i++)
		{
			cin >> x[i];
		}
		for (int i = 1; i <= n; i++)
		{
			pre[i] = max(pre[i - 1] + x[i - 1],x[i - 1]);
			ans = max(pre[i], ans);
		}
		cout << ans << "\n";
	}

}