s69_avançado.cpp

#include <bits/stdc++.h>
using namespace std;

const long long int maxn = 2e5+10, inf = 1e18;

long long int n, c, val[maxn], dp[maxn][2];

long long int solve(int u, int mod)
{
	if(dp[u][mod] != inf) return dp[u][mod]; //se ja calculei esse caso, retorno a dp

	if(u == n+1) return 0; //ja olhei todos os dias, então retorno 0

	long long int p1, p2;

	if(!mod) p1 = - val[u] - c + solve(u+1, 1);
	else p1 = val[u] + solve(u+1, 0);  

	p2 = solve(u+1, mod);

	return dp[u][mod] = max(p1, p2);
}

int main()
{
	while(cin >> n >> c)
	{
		for(int i = 0 ; i < maxn ; i++)
		{
			dp[i][0] = dp[i][1] = inf; //declaro que ainda não calculei nenhum dos casos, igualando todos a inf
		}

		for(int i = 1 ; i <= n ; i++) cin >> val[i];
	
		long long int resp = solve(1, 0);
		cout << resp << "\n";
	}
}