Buy Low, Sell High

#include <iostream>

const int N = 5 * (int)(1e5);
const int inf = 1e9;
int val[N];
int dp[2][N];

int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		std::cin >> val[i];
	}
	int cma = 0;
	int cmi = inf;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		cmi = std::min(cmi, val[i]);
		ans = std::max(ans, val[i] - cmi);
		dp[0][i] = ans;
	}
	ans = 0;
	for (int i = n-1; i >= 0; --i) {
		cma = std::max(cma, val[i]);
		ans = std::max(ans, cma - val[i]);
		dp[1][i] = ans;
	}
	ans = 0;
	for (int i = 0; i < n; ++i) {
		ans = std::max(ans, dp[0][i] + dp[1][i]);
	}
	std::cout << ans << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED