题干
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 * 1041 <= 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;
}没啥用放弃研究了，在研究也感觉意义不大
总结
对找下标i右边的最大值进行预先处理，达到复用。也算是记忆搜索的一种。属于简单题目。