问可获得的最大利润-买卖

EN

- We can go from `i` to `i + 1` and do nothing
- If we have Messi, we can sell him (setting `f0(i + 1) = max(f0(i + 1), f1(i) + price(i))`)
- If we don't have him and our budget is big enough, we can buy him  (doing `f1(i + 1) = max(f1(i + 1), f0(i) - price(i))`)

d[i] = p[i+1] - p[i]
d2[i] = d[i] - d[i-1]

// input
long predictionLength;
long budget;
bool startWithMessi;
long prediction[MAX_PREDICTION_LENGTH];

// output
long profit;

ifstream fin;
fin.open( DATA_FILE_NAME );
fin >> predictionLength >> budget >> startWithMessi;
for( long day = 0; day < predictionLength; day++ )
  fin >> prediction[day];
fin.close();

long money = budget;
bool messi = startWithMessi;
long dayIndex = 0;
while( dayIndex < predictionLength )
{
  if( messi )
  {
    if( dayIndex == predictionLength - 1
      || prediction[dayIndex] > prediction[dayIndex + 1] )
    {
      money += prediction[dayIndex];
      messi = false;
    }
  }
  else
    if( dayIndex < predictionLength - 1
      && prediction[dayIndex] < prediction[dayIndex + 1]
      && money >= prediction[dayIndex] )
    {
      money -= prediction[dayIndex];
      messi = true;
    }
  dayIndex++;
}

profit = money - budget;

cout << profit << endl;