给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j - i。
一对景点(i < j)组成的观光组合的得分为 values[i] + values[j] + i - j ,也就是景点的评分之和 减去 它们两者之间的距离。
返回一对观光景点能取得的最高分。
https://leetcode.cn/problems/best-sightseeing-pair/
/** Copyright (c) Huawei Technologies Co., Ltd. 2023-2023. All rights reserved.*/package com.huawei.prac;public class Solution14 {public static void main(String[] args) {int[] values = {8, 1, 5, 2, 6};System.out.println(maxScoreSightseeingPair(values));}/*** 1014【超时】. 最佳观光组合[逻辑转化 + 数学归纳]* sightseeing spots = values[i] + values[j] + i - j == (values[i] + i) + (values[j] - j)* 即 (values[i] + i) 取最大值** @param values 整数数组* @return 最高分*/public static int maxScoreSightseeingPair(int[] values) {int max = 0;int tmp = 0;for (int i = 0; i < values.length; i++) {max = Math.max(max, tmp + values[i] - i);tmp = Math.max(tmp, values[i] + i);}return max;}
}