Code : Reach End of Array With Max Score

class Solution {
  public:
    long long findMaximumScore(vector<int> &nums);
};

long long Solution::findMaximumScore(vector<int> &a) {
    int n = a.size();

    // dp[i] is the maximum score when you start at index i.
    vector<long long> dp(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            dp[i] = max(dp[i], 1LL * (j - i) * a[i] + dp[j]);
        }
    }
    return dp[0];
}

class Solution {
  public:
    long long findMaximumScore(vector<int> &nums);
};

long long Solution::findMaximumScore(vector<int> &a) {
    int n = a.size();

    long long speed = a[0], ans = 0;
    int last_cp = 0;
    for (int i = 1; i < n; i++) {
        // If you are given the option of upgrading the car, you should
        // always take it.
        // The last index is always a checkpoint.
        if (a[i] >= speed || i == n - 1) {
            ans += speed * (i - last_cp);
            speed = a[i];
            last_cp = i;
        }
    }
    return ans;
}