백준 1912번. 연속합

1912번. 연속합

1. 문제

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

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

2. 입력

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

3. 출력

• 첫째 줄에 답을 출력한다.

4. 풀이

• dp로 풀었다.
• 숫자 배열과 dp 배열을 만들어 놓고 최선의 경우를 따졌다.
• 일반적인 dp는 마지막 값이 최선인데 음수가 있어서 그렇게 할 방법을 못 찾아서 최댓값을 찾는 방식으로 풀었다.
• 음수일 때만 처리해주었다.
• 음수 일때는 이 음수를 넣어도 넣는 게 이득인지 아니면 그냥 새로 시작하는 게 이득인지 고려하면 된다.
• if arr[n-1] < 0 then max(dp[n-2]+arr[n-1]+arr[n], arr[n]

5. 처음 코드와 달라진 점

• if arr[n] < 0 then dp[n] = arr[n] 등 여러 가지를 쓰긴 했는데 사실 별 의미 없어서 그냥 지웠다.
• 최댓값 찾기라서 큰 문제는 없었다.
• for문 안에 문장을 한 줄로 쓸 수도 있는데 오히려 가독성 떨어지는 것 같아서 그냥 if/else if로 썼다.

6. 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100000], dp[100000];

int main() {

	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		scanf_s("%d", &arr[i]);
	}

	dp[0] = arr[0];
	dp[1] = max(max(arr[0], arr[1]), arr[0]+arr[1]);

	for (int i = 2; i < n; i++){
		if (arr[i - 1] < 0)
			dp[i] = max(arr[i], dp[i - 2] + arr[i - 1] + arr[i]);
		else
			dp[i] = dp[i - 1] + arr[i];

	}

	int answer = dp[0];

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

	cout << answer<<endl;
}