# [Gold IV] A[j]-A[i]+A[l]-A[k] [문제 링크](https://www.acmicpc.net/problem/15487) ## 문제 설명 <p>크기가 N인 배열 A가 주어졌을 때, i < j < k < l을 만족하는 (i, j, k, l) 중에서 A[j]-A[i]+A[l]-A[k]의 최댓값을 구하는 프로그램을 작성하시오. </p> ## 입력 <p>첫째 줄에 배열 A의 크기 N(4 ≤ N ≤ 1,000,000)이 주어진다.</p> <p>둘째 줄에는 배열 A에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1,000,000보다 작거나 같은 자연수이다.</p> ## 출력 <p>첫째 줄에 i < j < k < l을 만족하는 (i, j, k, l) 중에서 A[j]-A[i]+A[l]-A[k]의 최댓값을 출력한다.</p> ## 풀이 전형적인 N * 4 DP 문제입니다. dp[i]를 i개까지 선택했을 때의 최댓값으로 두고 풀었습니다. ``` c++ #include<bits/stdc++.h> using namespace std; const int MINF = -0x3f3f3f3f; int dp[5], curDp[5]; int main() { ios::sync_with_stdio(0); cin.tie(0); fill(dp+1, dp+5, MINF); int n; cin >> n; while(n--) { int val; cin >> val; for(int i=1;i<=4;i++) curDp[i] = max(dp[i], dp[i-1] + (i%2 ? -val : val)); memcpy(dp, curDp, sizeof dp); } cout << dp[4]; } ```