#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
int memo[2010][2010];
bool done[2010][2010];
vector<int> height;
int dp(int s, int e)
{
if (s > e) return 0;
if (done[s][e]) return memo[s][e];
done[s][e] = true;
int ans = 1;
ld maxhei = -99999999999.9;
int pre = s;
for (int i = s+1; i <= e; i++)
{
ld newhei = (height[i]-height[s])/(ld)(i-s);
if (newhei >= maxhei)
{
ans+=dp(pre+1, i-1);
pre = i;
maxhei = newhei;
}
}
ans+=dp(pre+1, e);
ans = max(ans, dp(s+1, e));
return memo[s][e] = ans;
}
int maximum_deevs(vector<int> y) {
int n = y.size();
height = y;
return dp(0, n-1);
}
