1014. Best Sightseeing Pair

LeetCode medium original: C# #array #backtracking #csharp #leetcode #math #medium
Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.
LeetCode Static

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

Beispiel:

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

Output: 11

C# Lösung

zugeordnet/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++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen 
#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 Lösung

zugeordnet/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 Lösung

zugeordnet/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 Lösung

zugeordnet/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 Lösung

zugeordnet/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
}

Algorithm

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

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

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

Проход по Arrayу:

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

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

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

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

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

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen
Es gibt noch keine aktiven Stellen.