Buy Low, Sell High

#include <iostream>

using namespace std;
typedef long long ll;

int n;
ll t[500005];
ll dp[500005];

ll res = 0;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> t[i];
	}
	ll cmi = 1000000005;
	for (int i = 0; i < n; ++i) {
		cmi = min(t[i], cmi);
		dp[i] = t[i]-cmi;
		if (i > 0) dp[i] = max(dp[i], dp[i-1]);
	}
	ll cmx = 0;
	ll rb = 0;
	for (int i = n-1; i >= 0; --i) {
		cmx = max(t[i], cmx);
		ll cr = cmx-t[i];
		rb = max(rb, cr);
		res = max(res, dp[i]+rb);
	}
	cout << res << "\n";
	return 0;
}

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