[C/C++] 백준 - 13998번 (연속합 2)

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

13398번: 연속합 2

문제

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

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

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

 

전에 풀었던 연속합 문제에서 조금 더 업그레이드(?) 된 문제이다

-> 연속합 문제 https://wonsjung.tistory.com/66?category=949214

[C/C++] 백준 - 1912번 (연속합)

이번에는 연속합을 구할 때 하나의 수를 제거했다고 하고 그 수를 건너띄고 다음 수까지 진행해서 최대합을 구하는 문제이다. 제거하지 않아도 됨.

 

똑같이 DP를 통해 풀어야하는데 나는 

1. 전에 풀었던 연속합에 사용했던 DP기법을 저장해주는 변수

2. 하나의 수를 제거해도 되기 때문에 제거한 후에 더해지는 최대값을 저장해주는 변수

해서 2차원 배열로 설정하였다.

int N; cin >> N;
for(int i=0;i<N;i++) cin >> a[i]; // a배열은 n개의 정수로 이루어진 수열

int DP[100001][2] = {0,}; 
// i,j라고 했을 때 j가 0인 곳에는 연속합1 기법 DP를 저장
// j가 1인 곳에는 현재 a[i]값을 더하지 않고, 바로 전 DP[i-1][0]과 비교해서 큰 값을 저장해주는 배열

 

초기 정답값을 a[0]으로 설정하고, i가 0부터 N-1까지 진행하면서 최대값을 갱신시켜주면 된다.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define INF 98765
#define swap(type,x,y) do{type t=x;x=y;y=t;} while(0)

using namespace std;

int DP[100003][2];
int a[100003];
int N;

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

	cin >> N;
	for (int i = 0; i < N; i++) cin >> a[i];
	int Answer = a[0];
	for (int i = 0; i < N; i++) {
		DP[i][0] = DP[i][1] = a[i];
		if (i == 0) continue;
		DP[i][0] = max(DP[i - 1][0] + a[i], a[i]);
		DP[i][1] = max(DP[i - 1][0], DP[i - 1][1] + a[i]);
		Answer = max({Answer, DP[i][0], DP[i][1]});
	}
	cout << Answer << endl;

	return 0;
}