java leetcode之[动态规划 中等] 1014. 观光组合

题目的链接在这里：https://leetcode-cn.com/problems/best-sightseeing-pair/submissions/

题目大意

一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

一、示意图

二、解题思路

动态规划

动态规划

代码如下：

class Solution {public int maxScoreSightseeingPair(int[] values) {//value表示第i个观光景点的评分 一对观光景点的最高分是 i<j values[i]+values[j]+(i-j)//变成了 values[i]+i 和value[j]-j 求最高分//dp[i]表示以i作为第二个观景点的 最大值 那dp[i]就等于  value[i]-i+value[j]+j 0<=j<i//所以dp[i]中的 value[i]-i是固定的 其实就变成了 找小于i里的最大值j作为dp[i]了 然后maxScore就记录每次的最大值int len=values.length;int max=values[0]+0;int maxScore=Integer.MIN_VALUE;for(int i=1;i<len;i++){//当i等于i时候就不必说了 之后 的话max都会进行更新maxScore=Math.max(values[i]-i+max,maxScore);//每次都是max和当前的值能构成的max进行比对max=Math.max(max,values[i]+i);}return maxScore;}
}