(array, can be dp)1014. Best Sightseeing Pair

T: O(n)

S: O(1)

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxPastValue = values[0]-1; // why -1? because we'll start from index 1, so value - dist (in this way, it will cal the j - i part!)
        int result = Integer.MIN_VALUE;
        for (int i = 1; i < values.length; i++) {
            result = Math.max(result, maxPastValue + values[i]);
            maxPastValue = Math.max(maxPastValue, values[i])-1; //for next value to use(in this way, it will cal the j - i part!)
        }
        return result;
    }
}

/***

Naive T: O(n^2)

O(n), array:
can we have a o(n) solution? we want 2 max values, but smaller dist.

I mean move elemnts, but look back a max element before? (save a max_value)
so we can also cal this dist!


(in this way, it will cal the j - i part!)
intit: pastMax = values[0] - 1

max(pastMax, values[i])-1

 */