Find the Best Sightseeing Pair - Coding

Given an integer array arr[] where arr[i] represents the value of the ith sightseeing spot. Two sightseeing spots i and j have a distance j – i between them. The score of a pair (i < j) of sightseeing spots is arr[i] + arr[j] + i – j: the sum of arr[]of the sightseeing spots, minus the distance between them. Find the maximum score of a pair of sightseeing spots.

Examples:

Input: arr[]= {8, 1, 5, 2, 6}
Output: 11
Explanation: For i = 0, j = 2, arr[i] + arr[j] + i – j = 8 + 5 + 0 – 2 = 11

Input: arr= [1, 2]
Output: 2
Explanation: For i = 0, j = 1, arr[i] + arr[j] + i – j = 2 + 1 + 0 – 1 = 2

Approach: To solve the problem, follow the below idea:

Since our task is to find max{ (arr[i]+i) + (arr[j]-j) } for all i<j.

So we can say that we want maximum of arr[i]+i and maximum of arr[j]-j.

Subproblem: find max (arr[i]-i) after i.
Recurrence Relation: max_after(i) = max{ arr[i]-i, max_after(i+1) }.
Finally ans would be maximum of arr[i]+i+max_after(i+1).

Step-by-step algorithm:

Maintain an array max_after[], such that max_after[i] stores the maximum value of arr[j] – j among all j >= i.
Now, iterate from 0 to N – 1, and for every index i store the maximum value of arr[i] + i + max_after[i] and store it in ans.
Return ans as the final answer.

Below is the implementation of the above algorithm:

C++

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

int maxScoreSightseeingPair(vector<int>& arr)
{
    // This function finds the best sightseeing pair in a
    // city represented by an array values.
    //  - max_after: stores the maximum sightseeing score
    //  obtainable starting from city i+1

    int N = arr.size();
    vector<int> max_after(N, 0);

    // Initialize max_after for the last city (no city after
    // it).
    max_after[N - 1] = arr[N - 1] - (N - 1);

    // Fill max_after array in reverse order.
    for (int i = N - 2; i >= 0; i--) {
        max_after[i] = max(max_after[i + 1], arr[i] - i);
    }

    int ans = 0;
    // Iterate through all cities except the last one.
    for (int i = 0; i < N - 1; i++) {
        // Calculate the total sightseeing score for the
        // current city and its best pairing city (i+1).
        ans = max(ans, arr[i] + i + max_after[i + 1]);
    }

    return ans;
}

int main()
{
    // Driver code to test the function
    vector<int> arr = { 8, 1, 5, 2, 6 };

    int maxScore = maxScoreSightseeingPair(arr);
    cout << "Max sightseeing score: " << maxScore << endl;
    return 0;
}

Java

import java.util.Arrays;

public class MaxScoreSightseeingPair {
    public static int maxScoreSightseeingPair(int[] arr)
    {
        // This function finds the best sightseeing pair in
        // a city represented by an array values.
        //  - maxAfter: stores the maximum sightseeing score
        //  obtainable starting from city i+1

        int N = arr.length;
        int[] maxAfter = new int[N];

        // Initialize maxAfter for the last city (no city
        // after it).
        maxAfter[N - 1] = arr[N - 1] - (N - 1);

        // Fill maxAfter array in reverse order.
        for (int i = N - 2; i >= 0; i--) {
            maxAfter[i]
                = Math.max(maxAfter[i + 1], arr[i] - i);
        }

        int ans = 0;
        // Iterate through all cities except the last one.
        for (int i = 0; i < N - 1; i++) {
            // Calculate the total sightseeing score for the
            // current city and its best pairing city (i+1).
            ans = Math.max(ans,
                           arr[i] + i + maxAfter[i + 1]);
        }

        return ans;
    }

    public static void main(String[] args)
    {
        // Driver code to test the function
        int[] arr = { 8, 1, 5, 2, 6 };

        int maxScore = maxScoreSightseeingPair(arr);
        System.out.println("Max sightseeing score: "
                           + maxScore);
    }
}

// This code is contributed by Shivam

Python

def max_score_sightseeing_pair(arr):
    N = len(arr)
    max_after = [0] * N

    max_after[N - 1] = arr[N - 1] - (N - 1)

    for i in range(N - 2, -1, -1):
        max_after[i] = max(max_after[i + 1], arr[i] - i)

    ans = 0
    for i in range(N - 1):
        ans = max(ans, arr[i] + i + max_after[i + 1])

    return ans


# Driver code to test the function
arr = [8, 1, 5, 2, 6]
max_score = max_score_sightseeing_pair(arr)
print("Max sightseeing score:", max_score)

JavaScript

// Function to calculate the maximum score for a sightseeing pair
function maxScoreSightseeingPair(arr) {
    // Get the length of the array
    const N = arr.length;
    // Initialize an array to store the maximum values after each index
    const maxAfter = new Array(N).fill(0);

    // Calculate the maximum value after each index
    maxAfter[N - 1] = arr[N - 1] - (N - 1);
    for (let i = N - 2; i >= 0; i--) {
        maxAfter[i] = Math.max(maxAfter[i + 1], arr[i] - i);
    }

    // Initialize a variable to store the maximum score
    let ans = 0;
    // Iterate through the array to find the maximum score
    for (let i = 0; i < N - 1; i++) {
        ans = Math.max(ans, arr[i] + i + maxAfter[i + 1]);
    }

    // Return the maximum score
    return ans;
}

// Driver code to test the function
const arr = [8, 1, 5, 2, 6];
const maxScore = maxScoreSightseeingPair(arr);
console.log("Max sightseeing score:", maxScore);

// This code is contributed by Shivam Gupta

Output

Max sightseeing score: 11

Time complexity: O(N), where N is the size of input subarray arr[].
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Array Data Structure Guide
Array Rearrangement
Array Order Statistics
Array Range Queries
Searching in Array

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	13