1014. Best Sightseeing Pair

LeetCode medium original: C# #array #backtracking #csharp #leetcode #math #medium
题目文本会按所选界面语言从俄语翻译；代码保持不变。
LeetCode Static

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

示例:

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

Output: 11

C# 解法

匹配/原始 
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++ 解法

自动草稿，提交前请检查 
#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 解法

匹配/原始 
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 解法

匹配/原始 
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 解法

匹配/原始 
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 解法

匹配/原始 
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 при проходе по 数组у.

Проход по 数组у:

Пройдитесь по 数组у начиная с первого 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 как максимальную оценку пары достопримечательностей.

😎

Vacancies for this task

活跃职位 with overlapping task tags are 已显示.

所有职位
目前还没有活跃职位。