动态规划：最佳观光组

文章目录

• 最佳观光组
• • 题目前置要求
  • 题干
  • 解题思路
  • 提及一下：前缀最值
  • 步骤
  • 代码实现（js）

最佳观光组

题目前置要求

做此题之前建议先学会了 动态规划：前缀最值

题干

给定一个数组values ,values[i]表示第i个观光景点的评分，并且两个景点i和j之间的距离为j-i，一对观光景点组成的得分为values[i] + values[j] + i-j,
也就是观光景点的评分之和减去他们两者之间的距离。
求一对观光景点能取得的最高分。

values=[8,1,5,2,6]// 答案 ： 11

解题思路

1. 拆分一下表达式为：values[i]+i + values[j]-j

2. 求出前缀最大值数组preMax[]

3. 递推values最佳观光组

提及一下：前缀最值

简单提一下。假如给定一个数组，rawArr = [7,3,5,1,8,4]。对于下标i,i可以是数组中的任意一个下标。我们期望的最值结果是：在下标0到i区间中，rawArr[i]是最大值，即下标i对应的值为区间最大值或最小值。例如区间前缀最小值最值结果：rawArr1 = [7,3,3,1,1]，区间前缀最大值最值结果：rawArr2 = [7,7,7,8,8]

步骤

1. 拆分表达式成两个部分:values[i]+i, values[j]-j，那么就可以分开为两次计算，简化计算过程的时间复杂度。如果不分开的话，那么计算过程中可能就需要进行循环嵌套了，类似冒泡排序，相对来说时间复杂度会高一些。

2. 先计算values[i]+i这部分的前缀最大值。前缀最值越往后值越大，这一遍，就可以得到从下标0至i景点为止values[i]+i的最大值

3. 然后再遍历一遍values[j]-j,j必须从1开始遍历，因为第一个景点最少要和第二个景点才能组成一组。接着取遍历过程中的最大值maxVal=max(maxVal,prev[j-1]+values[j]-j)，就是我们要的答案了

代码实现（js）

function bestViewGroup(){/*给定一个数组values values[i]表示第i个观光景点的评分，并且两个景点i和j之间的距离为j-i，一对观光景点组成的得分为values[i] + values[j] + i-j,也就是观光景点的评分之和减去他们两者之间的距离求一对观光景点能取得的最高分*/values=[8,1,5,2,6]// 答案 ： 11//将 values[i] + values[j] + i-j 拆分为 两个部分 values[i]+i 和 values[j]-j,只要取两部分最大，就可以得到一组观光景点的最高分preMax = []values.forEach((item,index)=>{if(index == 0){preMax[index] = item}else{preMax[index] = max(preMax[index-1],item+index)}})//遍历结果maxVal = 0values.forEach((item,j)=>{if(j == 0){// 什么也不做，因为从第一个要和最少第二和组成一组}else{maxVal = max(maxVal,preMax[j-1] + item-j)}})return "一组观光景点的最高分："+maxVal
}
function max(a,b){return a > b ? a : b
}
document.write(bestViewGroup()) // 答案 11