1014. Best Sightseeing Pair

LeetCode medium original: C# #array #backtracking #csharp #leetcode #math #medium
선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.
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 표시됨.

전체 채용
아직 활성 채용이 없습니다.