Best Sightseeing Pair - Solution & Explanation

This approach iterates through each index in the array as a starting point and computes the score for every subsequent point. It keeps track of the maximum score found.

Although simple, this approach involves nested iteration, making it inefficient for large inputs due to the O(n^2) time complexity.

The solution uses a nested loop to brute-force calculate the score for each pair of sights (i < j). The outer loop fixes 'i' while the inner loop iterates over 'j', calculates the respective score, and updates the maximum score found.

This approach is a much more efficient O(n) solution. It maintains a running maximal value of 'values[i] + i' to maximize the score of subsequent elements. As the array is traversed, it calculates and continuously updates the maximum possible score using this running maximum and 'values[j] - j'.

This optimized C solution iterates through the array, maintaining the maximal 'values[i] + i' seen so far and computing the current potential maximum score with 'values[j] - j'. The highest score is updated dynamically.