力扣（leetcode）每日一题 1014 最佳观光组合

题干

1014. 最佳观光组合

给你一个正整数数组 values，其中 values[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

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

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

示例 1：

**输入：**values = [8,1,5,2,6]
**输出：**11
**解释：**i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11

示例 2：

**输入：**values = [1,2]
**输出：**2

提示：

2 <= values.length <= 5 * 104
1 <= values[i] <= 1000

解法

两个点，一个start,一个end，start点的位置小于end。
可以得出start点的价值就是 values[i] + i 景点价值加上本身位置价值。
end点的价值就是 values[j] - j 景点价值减去本身位置价值
这样只要把两个列表的值相加得到最大就可以了公式如下 Max( startArr[i] + endArr[j]) j>i求最大值可以预先生成

for (int i = length - 2; i >= 0; i--) {  endArr[i] = Math.max(endArr[i], endArr[i + 1]);
}

这样可以将复杂度从LogN^N降低到logN


public static int maxScoreSightseeingPair(int[] values) {  int length = values.length;  int[] startArr = new int[length];  int[] endArr = new int[length];  for (int i = 0; i < length; i++) {  startArr[i] = values[i] + i;  endArr[i] = values[i] - i;  }  // start i + end j  //    // 确定了i  需要找end这边的最大值  for (int i = length - 2; i >= 0; i--) {  endArr[i] = Math.max(endArr[i], endArr[i + 1]);  }  int max = Integer.MIN_VALUE;  for (int i = 0; i < length - 1; i++) {  int value = startArr[i] + endArr[i + 1];  max = Math.max(max, value);  }  return max;  
}

优化一下写法
节省一个数组空间，节省一次遍历，然后变量写的抽象些

  
public static int maxScoreSightseeingPair(int[] values) {  int[] endArr = new int[values.length];  for (int i = values.length - 1; i >= 0; i--) {  if (i == values.length - 1) {  endArr[i] = values[i] - i;  } else {  endArr[i] = Math.max(values[i] - i, endArr[i + 1]);  }  }  int max = Integer.MIN_VALUE;  for (int i = 0; i < values.length - 1; i++) {  max = Math.max(max, values[i] + i + endArr[i + 1]);  }  return max;  
}

在这里插入图片描述
优化后

空间上还可以进一步优化。从后往前遍历，用新的值覆盖旧的值来达到节约内存的目的


public static int maxScoreSightseeingPair(int[] values) {  int max = Integer.MIN_VALUE;  int maxright = values[values.length - 1] - (values.length - 1);  for (int i = values.length - 2; i >= 0; i--) {  max = Math.max(max, values[i] + i + maxright);  maxright = Math.max(values[i] - i, maxright);  }  return max;  
}

再优化一个空间值


public static int maxScoreSightseeingPair(int[] values) {  int max = Integer.MIN_VALUE;  values[values.length - 1] = values[values.length - 1] - (values.length - 1);  for (int i = values.length - 2; i >= 0; i--) {  max = Math.max(max, values[i] + i + values[i + 1]);  values[i] = Math.max(values[i] - i, values[i + 1]);  }  return max;  
}