백준 13398번, 연속합 2 풀이

문제

백준 13398번

풀이

그냥 연속한 수열에서 최댓값을 구하는 점화식은 $ dp[i] = max(dp[i] + arr[i], 0) $이라는 것을 알고 있습니다. ( ... ⓐ )

 

여기 다른 dp 배열을 하나 더 만들어, 수를 한번 제거하였을 때의 최댓값도 같이 관리해줍니다. ( ... ⓑ )

 

그러면, ⓐ의 DP 배열을 $ A $, ⓑ의 DP 배열을 $ B $라고 하면, $ A $는 위 점화식으로 쉽게 채워줄 수 있습니다.

 

$ B = max(A[i - 1], B[i - 1] + arr[i]) $라는 점화식으로 나타낼 수 있습니다.

 

$ A_i $까지 더한 합에서 $ i $만 제하는 경우

또는

$ B_i $에서(이미 한번 뺀 경우) 현재 값을 더해준 경우로 두 가지로 나뉘기 때문에 위와 같은 점화식이 나옵니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;
using namespace views;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef unordered_map<int, int> mpii;

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

	int n, f = 0; cin >> n;
	vi vec(n + 1);
	vector<vi> dp(n + 1, vi(2));

	for (auto &i : vec | drop(1)) cin >> i, f = f || i >= 0;

	if (!f) {
		cout << *max_element(vec.begin() + 1, vec.end());
		return 0;
	}

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		dp[i][0] = max(dp[i - 1][0] + vec[i], 0);
		dp[i][1] = max(dp[i - 1][1] + vec[i], dp[i - 1][0]);

		ans = max(ans, max(dp[i][0], dp[i][1]));
	}

	cout << ans;
}