济南网站建设sdjy6,wordpress 上传图片大小,西城网站建设公司,用模板快速建站给定正整数数组 A#xff0c;A[i] 表示第 i 个观光景点的评分#xff0c;并且两个景点 i 和 j 之间的距离为 j - i。
一对景点#xff08;i j#xff09;组成的观光组合的得分为#xff08;A[i] A[j] i - j#xff09;#xff1a;景点的评分之和减去它们两者之间…给定正整数数组 AA[i] 表示第 i 个观光景点的评分并且两个景点 i 和 j 之间的距离为 j - i。
一对景点i j组成的观光组合的得分为A[i] A[j] i - j景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。 示例
输入[8,1,5,2,6] 输出11 解释i 0, j 2, A[i] A[j] i - j 8 5 0 - 2 11
提示
2 A.length 50000 1 A[i] 1000
思路动态规划
拆分题目要求拆为A[i]i,A[j]-j
维护A[i]i的最大值依次遍历找到和最大的两个值
例如[8,1,5,2,6]
max8res8-118
max8, res8-2511
.....
代码
class Solution { public int maxScoreSightseeingPair(int[] A) { int res0; int max A[0]; for(int i1;iA.length;i){ res Math.max(res,maxA[i]-i); max Math.max(max,A[i]i); } return res; }
}
