[백준 13398] 연속합 2

문제 링크 => 13398번: 연속합 2 (acmicpc.net)

13398번: 연속합 2

---

다이나믹 프로그래밍 문제이다.

 

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

 

수는 한개 이상 선택해야 하고, 수열에서 수를 하나 제거할 수 있다. (제거하지 않아도 된다)

 

이때 수를 제거하지 않고 얻어낼 수 있는 최댓값과 수열에서 수를 하나 제거하여 얻을 수 있는 최댓값 두가지로 분류하여 구해내야 한다.

 

수를 제거하지 않고 얻어낼 수 있는 방법

=> dp[x][0] = max(dp[x-1][0] + arr[x], arr[x])

 

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 로 표기해본다면 다음과 같다

[10, 6, 9, 10, 15, 21, -14, -2, 19, 18]  <=  수를 제거하지 않고 얻어낸 방법

 

수를 하나 제거하여 얻을 수 있는 방법

=> dp[x][1] = max(dp[x-1][1] + arr[i], dp[i-1][0])

 

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 로 표기해본다면 다음과 같다

[10, 6, 9, 10, 15, 21, 21, 33, 54, 53] <= 수를 하나 제거하여 얻을 수 있는 방법

 

이때 최종적인 최댓값(result) => result = max({result, dp[i][0], dp[i][1]}) 

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define MOD 1000000009

using namespace std;

int dp[100001][2]; // 그대로 or 하나 빼기
int arr[100001];

void solve(int n) {
	int ans = dp[1][0] = dp[1][1] = arr[1];
	for (int i = 2; i <= n; i++) {
		dp[i][0] = max(dp[i - 1][0] + arr[i], arr[i]);
		dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i-1][0]);
		ans = max({ ans,dp[i][0],dp[i][1] });
	}
	cout << ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

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

	return 0;
}