문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

풀이

첫번째 도전

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>

using namespace std;

int main()
{
	int n; 
	cin >> n;
	vector<int> vec;
	vector<int> dp;


	for (int i = 0; i < n; i++)
	{
		int value;
		cin >> value;
		vec.push_back(value);
	}

	int maxn = numeric_limits<int>::lowest();
	for (int i = 0; i < n; i++) {
		int partial_sum = 0;
		for (int j = i; j < n; j++) {
			partial_sum += vec[j];
			maxn = max(partial_sum, maxn);
		}
	}
	
	cout << maxn << endl;

	return 0;
}

모든 경우의 수를 고려하도록 코드를 짜보았다. 하지만 이 경우에는 시간초과가 나왔다. 그 이유는 입력으로 최대 100,000개의 정수가 들어올 수 있는데 이 경우 이중 for문을 사용하면 시간 복잡도는 $O(n^2)$으로 최대 10,000,000,000 100억으로 1초이상 시간이 걸린다.

참고 numeric_limits::lowest()

이 코드는 정수에서 가장 작은 수를 할당하는 것으로 정수에서 가장 작은 수인 약 -21억 정도의 값을 할당시킨다. 이 코드를 실행하기 위해서는 limits 라이브러리를 include해줘야한다.

두번째 도전

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int n; 
	cin >> n;
	vector<int> vec;
	vector<int> dp;


	for (int i = 0; i < n; i++)
	{
		int value;
		cin >> value;
		vec.push_back(value);
	}

	dp.push_back(vec[0]);
	for (int i = 1; i < n; i++){
		dp.push_back(max(vec[i], dp[i-1] + vec[i]));	
	}
	int dp_max = *max_element(dp.begin(), dp.end());

	cout << dp_max << endl;
	
	return 0;
}

이는 이중 for문이 아닌 단일 for문으로 시간 복잡도가 $O(n)$이 되어 최대 100,000이 되어 1초가 걸리지 않는다. 단일 for문으로 문제를 해결하기 위해서는 새로운 숫자를 볼 때 이전까지의 최대합 + 새로운 숫자와 새로운 숫자와의 크기 비교를 통해 둘 중 큰 수를 벡터 배열 dp에 저장한다. 그리고 마지막에 벡터 배열 dp에서 가장 큰 수를 추출하면 정답이 된다. 직관적으로 설명하면 숫자를 한번 순회하면서 최대 연속합을 찾는데 계속 연속합으로 가져가는게 좋을지 아니면 새로 연속합을 시작하는게 좋을지를 판단해나가면서 문제를 해결하는 것이다.