[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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

입력 1

10
10 -4 3 1 5 6 -35 12 21 -1

출력 1

33

1. 문제 설명

• 크게 2가지 방법으로 풀 수 있다.
  두 방법은 조건만 다를 뿐이지 실제로 메인 방식은 같다.

• 대신 아래 답을 보기전에 아래 나온 문제의 함정을 이해하면 소스를 보기 편하다!

• 당~연히 음수를 더하면 값이 떨어진다. 그래서 일부러 음수가 나오면 더하지 않고 프로그램을 짜는 경우가 있는데 이 경우 함정에 빠진것이다. 위 사진은 반례의 예시이다.
  (추가적으로 문제에서 단, 수는 한 개 이상 선택해야 한다.의 뜻은 값 하나만 선택해도 된다는 뜻이다. 나는 이것을 ‘연속으로 선택할 수 있는 수는 무조건 한 개 이상 선택해야 한다’ 라고 이해해서 문제를 푸는데 굉장히 오래 걸렸다.)

1. 10 -4 3 일 경우 3개를 모두 더하면 9가 나온다. 그래서 그냥 10만 선택하는것이 max 값.
2. 10 -3 3 일 경우 3개를 모두 더하면 10이 나온다. 그래서 10을 선택하는것이 max 값.
3. 10 -2 3 일 경우 3개를 모두 더하면 11이 나온다. 그래서 세개를 다 더한 값인 11이 max 값.

• 점화식은 단순히 연속된 부분의 합을 구하는 것이니 간단하다.

• [점화식]
  dp[i] = dp[i] + dp[i - 1]

1-1. 이전 합을 더한 값이 양수일때만 더하는 방법.

1. 현재 값과 이전 합을 더했을 때 음수 혹은 0이 나오면 일반적인 양수를 선택하는 것보다 결과값이 못하게 나오니 선택할 필요가 없다.
2. 이전의 합이 음수라면 선택할 필요 없이 지금부터 다시 선택해 나가면 된다.

• [주요 코드]

   if (dp[i-1] > 0 && dp[i] + dp[i-1] > 0) {
   	dp[i] += dp[i-1];
   }
  

1-2. 이전 합을 더한 값이 현재값보다 못할 경우 더하지 않는 방법.

• 위 방법과 같지만 어감이 다를뿐이다. 위 방법은 0을 기준으로 삼았지만, 이 방법은 현재 값을 기준으로 삼았다.

• 현재 값과 이전 합을 더했을 때 현재 값 보다 작다면 선택할 필요가 없다.

• [주요 코드]

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

2. 소스코드

[1-1]방식의 소스코드

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

using namespace std;

int main() {
	int n, MAX;

	cin >> n;

	vector<int> dp(n + 1, 0);

	for (int i = 1; i <= n; i++) {
		cin >> dp[i];
	}

	MAX = dp[1];

	for (int i = 2; i <= n; i++) {
		if (dp[i - 1] > 0 && dp[i] + dp[i - 1] > 0) {
			dp[i] += dp[i - 1];
		}

		MAX = max(MAX, dp[i]);
	}

	cout << MAX << endl;

	return 0;
}

[1-2]방식의 소스코드

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

using namespace std;

int main() {
	int n, MAX;

	cin >> n;

	vector<int> dp(n + 1, 0);

	for (int i = 1; i <= n; i++) {
		cin >> dp[i];
	}

	MAX = dp[1];
	
	for (int i = 2; i <= n; i++) {
		dp[i] = max(dp[i - 1] + dp[i], dp[i]);
		MAX = max(MAX, dp[i]);
	}

	cout << MAX << endl;

	return 0;
}