백준 15487(A[j]-A[i]+A[l]-A[k])

www.acmicpc.net/problem/15487

15487번: A[j]-A[i]+A[l]-A[k]

구현이 진짜 어려웠던 문제

 

난 아직 인덱스 처리가 익숙치 않나보다. 생각정리만 좀 하면 바로 풀 수 있는 문제를 진짜 한 세네시간 헤맨듯?

단순하게 쪼개서 생각해주면 된다.

 

0~1까지 최대 

0~j까지 최대를 저장하고, 

 

j+1 ~ N까지 최대를 하나하나 저장한 뒤에

 

인덱스를 잘 지지고 볶아서 j는 1에서 N-2까지 이동하면서 최대를 출력하면 된다. 

지금 생각해보니 더 쉬운것 같기도? 

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 1000005
#define INF 987654321

int num[MAX];
int ldp[MAX];
int rdp[MAX];
int N;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	int max_n = -INF;
	int min_n = INF;
	ldp[0] = -INF;
	rdp[N - 1] = -INF;
	for (int i = 0; i < N - 1; i++) {
		if (i) {
			ldp[i] = max(ldp[i - 1], num[i] - min_n);
		}
		min_n = min(min_n, num[i]);
	}
	max_n = num[N - 1];
	for (int i = N - 2; i > 1; i--) {
		rdp[i] = max(rdp[i + 1], max_n - num[i]);
		max_n = max(max_n, num[i]);
	}
	int ans = -INF;
	for (int i = 1; i < N - 2; i++) {
		ans = max(ans, ldp[i] + rdp[i + 1]);
	}
	cout << ans;
}