백준 15487번, A[j]-A[i]+A[l]-A[k] 풀이

문제

백준 15487번

풀이

임의의 인덱스 $ a $를 기준으로 나누었다고 가정해봅시다.

이제 두 구간 $ [1, a] $에서 $ -A[i] + A[j] $의 최댓값과, $ (a, N] $에서 $ -A[l] + A[k] $의 최댓값을 구하면 됩니다.

 

$ a $를 기준으로 왼쪽 구간의 최댓값의 배열과 오른쪽 구간의 최댓값의 배열을 각각 $ L, R $이라고 두면, 범위가 늘어날수록 최댓값이 점점 커지므로 투포인터 같은 DP로 $ L, R $을 $ O(N) $에 채워줄 수 있습니다.

 

그러면, 모든 $ i $에 대하여 $ L[i] + R[i + 1] $의 최댓값이 정답이 됩니다. (양쪽으로 나누는 기준점이 포함되면, 중복으로 선택될 수 있기 때문에 양쪽 중 하나에서는 빼야합니다.)

소스코드

#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; cin >> n;
	vi vec(n + 1);
	for (auto &i : vec | drop(1)) cin >> i;

	vi L(n + 1, -1e9), R(n + 1, -1e9);
	int mn = 1e9, mx = -1e9;
	for (int i = 1; i <= n; i++) {
		mx = max(mx, vec[i]);
		if (mn != 1e9) L[i] = mx - mn;
		if (mn > vec[i]) {
			mn = vec[i];
			mx = -1e9;
		}
		if (mx != -1e9) L[i] = mx - mn;
	}
	mn = 1e9, mx = -1e9;
	for (int i = n; i >= 1; i--) {
		mn = min(mn, vec[i]);
		if (mx != -1e9) R[i] = mx - mn;
		if (mx < vec[i]) {
			mx = vec[i];
			mn = 1e9;
		}
		if (mn != 1e9) R[i] = mx - mn;
	}

	int ans = -1e9;
	for (int i = 1; i < n; i++) ans = max(ans, L[i] + R[i + 1]);
	cout << ans;
}