1014. Best Sightseeing Pair.cpp

/*
 ____  _     _           _     _       __  __       _ _           _
|  _ \(_)___| |__   __ _| |__ | |__   |  \/  | __ _| | |__   ___ | |_ _ __ __ _
| |_) | / __| '_ \ / _` | '_ \| '_ \  | |\/| |/ _` | | '_ \ / _ \| __| '__/ _` |
|  _ <| \__ \ | | | (_| | |_) | | | | | |  | | (_| | | | | | (_) | |_| | | (_| |
|_| \_\_|___/_| |_|\__,_|_.__/|_| |_| |_|  |_|\__,_|_|_| |_|\___/ \__|_|  \__,_|

*/

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

class Solution
{
public:
  int maxScoreSightseeingPair(vector<int> &values)
  {
    int result = 0, n = values.size();

    int a = values[0];
    for (int i = 1; i < n; i++)
    {
      result = max(result, a + values[i] - i);
      a = max(a, values[i] + i); // picking better A if available
    }
    return result;
  }
};