Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 11:27:25
Task:Buy Low, Sell High
Sender:Ukkonen Fan Club
Submission time:2018-05-26 11:27:25
Status:READY
Result:ACCEPTED

Show test data

Code

#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';
}