1014. Best Sightseeing Pair

leetcode medium

#array#backtracking#csharp#leetcode#math#medium

Task

Вам дан целочисленный массив values, в котором values[i] представляет собой значение i-й достопримечательности. Две достопримечательности i и j имеют расстояние j - i между собой. Оценка пары (i < j) достопримечательностей равна values[i] + values[j] + i - j: сумма значений достопримечательностей минус расстояние между ними. Возвращается максимальная оценка пары достопримечательностей.

Пример:

Input: values = [8,1,5,2,6]

Output: 11

C# solution

matched/original

public class Solution {
    public int MaxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int maxIPlusValue = values[0];
        
        for (int j = 1; j < values.Length; j++) {
            maxScore = Math.Max(maxScore, maxIPlusValue + values[j] - j);
            maxIPlusValue = Math.Max(maxIPlusValue, values[j] + j);
        }
        
        return maxScore;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxScoreSightseeingPair(vector<int>& values) {
        int maxScore = 0;
        int maxIPlusValue = values[0];
        
        for (int j = 1; j < values.size(); j++) {
            maxScore = max(maxScore, maxIPlusValue + values[j] - j);
            maxIPlusValue = max(maxIPlusValue, values[j] + j);
        }
        
        return maxScore;
    }
}

Java solution

matched/original

public class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int maxScore = 0;
        int maxIPlusValue = values[0];
        
        for (int j = 1; j < values.length; j++) {
            maxScore = Math.max(maxScore, maxIPlusValue + values[j] - j);
            maxIPlusValue = Math.max(maxIPlusValue, values[j] + j);
        }
        
        return maxScore;
    }
}

JavaScript solution

matched/original

class Solution {
    maxScoreSightseeingPair(values) {
        let maxScore = 0;
        let maxIPlusValue = values[0];
        
        for (let j = 1; j < values.length; j++) {
            maxScore = Math.max(maxScore, maxIPlusValue + values[j] - j);
            maxIPlusValue = Math.max(maxIPlusValue, values[j] + j);
        }
        
        return maxScore;
    }
}

Python solution

matched/original

class Solution:
    def maxScoreSightseeingPair(self, values: List[int]) -> int:
        max_score = 0
        max_i_plus_value = values[0]
        
        for j in range(1, len(values)):
            max_score = max(max_score, max_i_plus_value + values[j] - j)
            max_i_plus_value = max(max_i_plus_value, values[j] + j)
        
        return max_score

Go solution

matched/original

func maxScoreSightseeingPair(values []int) int {
    maxScore := 0
    maxIPlusValue := values[0]
    
    for j := 1; j < len(values); j++ {
        maxScore = max(maxScore, maxIPlusValue + values[j] - j)
        maxIPlusValue = max(maxIPlusValue, values[j] + j)
    }
    
    return maxScore
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализация переменных:

Инициализируйте переменную max_score для хранения максимальной оценки пары.

Инициализируйте переменную max_i_plus_value для хранения максимального значения выражения values[i] + i при проходе по массиву.

Проход по массиву:

Пройдитесь по массиву начиная с первого элемента и для каждого элемента values[j] вычислите текущую оценку пары как values[j] - j + max_i_plus_value.

Обновите значение max_score, если текущая оценка больше.

Обновите значение max_i_plus_value, если текущий элемент values[j] + j больше предыдущего max_i_plus_value.

Возврат результата:

Верните значение max_score как максимальную оценку пары достопримечательностей.

😎