백준 1912 c++ 연속합

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

1912번: 연속합

---

문제

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 <vector>
using namespace std;


int main()
{
	int N;
	cin >> N;
	vector<int> arr(N+1,0);
	vector<int> bp(N + 4, -1000);//오름차순의 최대 합
	vector<int> bp2(N + 4, -1000);//내림차순의 최대합
	for (int i=1; i < N + 1; i++)
	{
		cin >> arr[i];//모든 수열을 입력받는다
	}
	for (int i = 1; i < N + 1; i++)//오름차순 최대 합 구하기
	{
		bp[i] = arr[i];
		bp[i] = max(bp[i], bp[i - 1]+arr[i]);//자신만 있는것 vs 자신앞까지의 최대합+자신
	}
	for (int i = N; i > 0; i--)
	{
		bp2[i] = arr[i];
		bp2[i] = max(bp2[i], bp2[i + 1] + arr[i]);//자신만 있는것 vs 자신뒤까지의 최대합+자신
	}
	int result = -1000;
	for (int i = 1; i < N + 1; i++)
	{
		if (result < bp[i] + bp2[i] - arr[i])//오름차순 최대합 + 내림차순 최대합은 본인을 두 번 더하는 것이므로 본인을 한번 빼준다
			result = bp[i] + bp2[i] - arr[i];
	}
	cout << result;
}

---

수열

1

-100

3

4

를 생각해 보자

수열	1	-100	3	4
오름차순 최대합 dp	1	-99	3	7
내림차순 최대합 dp2	1	-93	7	4
결과 값	1+1-1  = 1	(-99)+(-93)-(-100)= -93	3+7-3 = 7	4+7-4 = 7

오름차순의 최대합 dp 의 경우 자신 이전까지의 수만을 생각한다

내림차순의 최대합 dp2의 경우 자신 뒤까지의 수만을 생각한다

이 두 값을 더해주고 본인을 한 번 빼준 값이 결과 값이다.