观光景点组合得分问题

问题描述

小R正在研究一组观光景点，每个景点都有一个评分，保存在数组 values 中，其中 values[i] 表示第 i 个观光景点的评分。同时，景点之间的距离由它们的下标差 j - i 表示。一对景点 (i < j) 的观光组合得分为 values[i] + values[j] + i - j，也就是两者评分之和减去它们之间的距离。

小R想知道，在哪种情况下能够获得观光景点组合的最高得分。

约束条件:

2 <= values.length

1 <= values[i] <= 1000

测试样例

样例1：

输入：values = [8, 3, 5, 5, 6]
输出：11

样例2：

输入：values = [10, 4, 8, 7]
输出：16

样例3：

输入：values = [1, 2, 3, 4, 5]
输出：8

解题思路

将每个景点的得分视为 values[i] + i，我们称之为 score_i。

将每个景点的得分视为 values[j] - j，我们称之为 score_j。

我们的目标是：最大化 score_i + score_j，其中 i < j。

代码实现

Cangjie

func solution(values: Array<Int64>) {
    var max_score = 0
    // let score_i = values[i] + i
    var max_value = values[0] + 0
    for (j in 1..values.size) {
        let score_j = values[j] - j
        max_score = max(max_score, max_value + score_j)
        max_value = max(max_value, values[j] + j)
    }
    max_score
}

main() {
    println(solution([8, 3, 5, 5, 6]) == 11)
    println(solution([10, 4, 8, 7]) == 16)
    println(solution([1, 2, 3, 4, 5]) == 8)
}

Rust

fn solution(values: Vec<i32>) -> i32 {
    let mut max_score = 0;
    let mut max_value = values[0] + 0;
    for j in 1..values.len() {
        let score_j = values[j] - j as i32;
        max_score = max_score.max(max_value + score_j);
        max_value = max_value.max(values[j] + j as i32);
    }
    max_score
}

 fn main() {
    println!("{}", solution(vec![8, 3, 5, 5, 6]) == 11);
    println!("{}", solution(vec![10, 4, 8, 7]) == 16);
    println!("{}", solution(vec![1, 2, 3, 4, 5]) == 8);
 }

Python

def solution(values):
    max_score = 0
    # 第一个景点的得分是 values[0] + 0
    max_value = values[0] + 0
    for j in range(1, len(values)):
        score_j = values[j] - j
        max_score = max(max_score, max_value + score_j)
        max_value = max(max_value, values[j] + j)
    return max_score

print(solution([8, 3, 5, 5, 6]) == 11)
print(solution([10, 4, 8, 7]) == 16)
print(solution([1, 2, 3, 4, 5]) == 8)

JavaScript

function solution(values) {
    let max_score = 0;
    let max_value = values[0] + 0;   
    for (let j = 1; j < values.length; ++j) {
        let score_j = values[j] - j;
        max_score = Math.max(max_score, max_value + score_j);
        max_value = Math.max(max_value, values[j] + j);
    }
    return max_score;
}

console.log(solution([8, 3, 5, 5, 6]) === 11 );
console.log(solution([10, 4, 8, 7]) === 16 );
console.log(solution([1, 2, 3, 4, 5]) === 8 );

复杂度分析

时间复杂度：O(n)，其中 n 是数组 values 的长度。我们只需要遍历一次数组。

空间复杂度：O(1)，我们只需要常数级别的额外空间。

仓颉编程语言