class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
}
};
1014. 最佳观光组合
给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例 1：
输入：values = [8,1,5,2,6] 输出：11 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
示例 2：
输入：values = [1,2] 输出：2
提示：
2 <= values.length <= 5 * 1041 <= values[i] <= 1000原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.5 MB, 提交时间: 2024-09-23 09:20:18
impl Solution {
pub fn max_score_sightseeing_pair(values: Vec<i32>) -> i32 {
let mut ans = 0;
let mut mx = 0; // j 左边的 values[i] + i 的最大值
for (j, &v) in values.iter().enumerate() {
ans = ans.max(mx + v - j as i32);
mx = mx.max(v + j as i32);
}
ans
}
}
javascript 解法, 执行用时: 68 ms, 内存消耗: 54.4 MB, 提交时间: 2024-09-23 09:20:03
/**
* @param {number[]} values
* @return {number}
*/
var maxScoreSightseeingPair = function(values) {
let ans = 0, mx = values[0]; // mx 表示 j 左边的 values[i] + i 的最大值
for (let j = 1; j < values.length; j++) {
ans = Math.max(ans, mx + values[j] - j);
mx = Math.max(mx, values[j] + j);
}
return ans;
};
golang 解法, 执行用时: 39 ms, 内存消耗: 7 MB, 提交时间: 2024-09-23 09:19:49
func maxScoreSightseeingPair(values []int) (ans int) {
mx := 0 // j 左边的 values[i] + i 的最大值
for j, v := range values {
ans = max(ans, mx+v-j)
mx = max(mx, v+j)
}
return
}
cpp 解法, 执行用时: 47 ms, 内存消耗: 42.4 MB, 提交时间: 2024-09-23 09:19:34
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int ans = 0, mx = values[0]; // mx 表示 j 左边的 values[i] + i 的最大值
for (int j = 1; j < values.size(); j++) {
ans = max(ans, mx + values[j] - j);
mx = max(mx, values[j] + j);
}
return ans;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 49.2 MB, 提交时间: 2024-09-23 09:19:12
class Solution {
public int maxScoreSightseeingPair(int[] values) {
int ans = 0;
int mx = values[0]; // j 左边的 values[i] + i 的最大值
for (int j = 1; j < values.length; j++) {
ans = Math.max(ans, mx + values[j] - j);
mx = Math.max(mx, values[j] + j);
}
return ans;
}
}
python3 解法, 执行用时: 124 ms, 内存消耗: 21.2 MB, 提交时间: 2024-09-23 09:19:01
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
ans = mx = 0 # mx 表示 j 左边的 values[i] + i 的最大值
for j, v in enumerate(values):
ans = max(ans, mx + v - j)
mx = max(mx, v + j)
return ans
python3 解法, 执行用时: 117 ms, 内存消耗: 21.2 MB, 提交时间: 2024-09-23 09:18:29
class Solution:
def maxScoreSightseeingPair(self, values: List[int]) -> int:
ans, mx = 0, values[0] + 0
for i in range(1, len(values)):
ans = max(ans, mx + values[i] - i)
mx = max(mx, values[i] + i)
return ans
golang 解法, 执行用时: 44 ms, 内存消耗: 7.2 MB, 提交时间: 2021-07-22 10:25:13
func maxScoreSightseeingPair(values []int) int {
ans, mx := 0, values[0] + 0
for i := 1; i < len(values); i++ {
ans = max(ans, mx + values[i] - i)
mx = max(mx, values[i] + i)
}
return ans
}
func max(x, y int) int {
if x > y {
return x
}
return y
}