연속합

---

완전탐색

가장 간단한 풀이이다.
i번째부터 j번째까지 더하는것이 답일것이다.
시간복잡도는 N^2, N=100,000이므로 10^10으로 시간초과가 난다.

---

DP

정답은 어느시점부터 i번째 까지 더한수가 정답일 것이다.
즉, i번째 숫자를 더했을때 연속합을 dp[i], ret라는 변수를 두고 최대값을 기록하면서 더해가자.

연속합이 최대인 경우이므로 dp[i]= max(dp[i-1]+number,number) 이다.

예를들어 3 5 6 -35 12 21 -1 일때
dp[1] = 3
dp[2] = max(3+5,5) = 8
dp[3] = max(8+6,6) = 14
dp[4] = max(14-35,-35) = -21
dp[5] = max(-21,12) = 12
dp[6] = max(12+21,21) = 33
dp[7] = max(33-1,-1) = 32

빨간색으로 칠한 부분에서 극대값들이 형성된다. 즉, 그것들중에 정답이 있다.

ret라는 변수를 도입해서 최대값을 기록하면된다.

이렇게되면 극대부분을 기록할수 있다.

---

실제 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>

using namespace std;
#define endl "\n"

#define MAX 100000+1
int N;
int dp[MAX];
int ret = -1000;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N;
	
	for (int i = 1; i <= N; i++)
	{
		int number;
		cin >> number;

		dp[i] = max(dp[i - 1] + number, number);
		ret = max(dp[i], ret);
	}

	cout << ret;
}

---

참고

https://yabmoons.tistory.com/16
https://yabmoons.tistory.com/514