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;
	cmi = 1000000005;
	for (int i = n-1; i >= 0; --i) {
		cmx = max(t[i], cmx);
		cmi = min(t[i], cmi);
		res = max(res, dp[i]+(cmx-cmi));
	}
	cout << res << "\n";
	return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED