package com.example.lettcode.dailyexercises;/** * @Class ScoreSightseeingPair * @Description 1014 最佳观光组合 * 给定正整数数组 A，A[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 * @Author 10256137 * @Date 2020/6/17 **/public class ScoreSightseeingPair {}

/** * 解法1:暴力求解, */public int maxScoreSightseeingPair(int[] A) {	if (A == null || A.length == 0) {		return 0;	}	int max = 0;	int len = A.length;	for (int i = 0; i < len - 2; i++) {		for (int j = i + 1; j < len - 1; j++) {			int temp = A[i] + A[j] + i - j;			max = max > temp ? max : temp;		}	}	return max;}

/** * 解法二： * 目的相当于(A[i]+i)+(A[j]-j) 获取最大值, * A[j]-j当遍历到当前元素j时便可取得, * A[i]+i相当于遍历过程中保存的最大结果 * 遍历一次即可得到最终结果 */public int maxScoreSightseeingPair(int[] A) {	if (A == null || A.length == 0) {		return 0;	}	int max_i = 0;	int max_j = 0;	for (int j = 0; j < A.length; j++) {		max_j = Math.max(max_j,A[j]+max_i-j);		max_i = Math.max(max_i, A[j]+j);	}	return max_j;}

/** * 解法3:利用动态规划 * 设 res 为最终结果，dp[i] 为位置i为第二个元素时对应的最高分 * 对于 i >= 2, dp[i]仅取决于与 A[i - 1] 的分数 和 相对于 dp[i - 1] 的景点的分数，即 * 
 * dp[i] = max(dp[i - 1] - A[i - 1] + A[i] - 1, A[i] + A[i - 1] - 1); */public int maxScoreSightseeingPair(int[] A) {	if (A == null || A.length == 0) {		return 0;	}	int[] dp = new int[A.length];	dp[0] = A[0];	dp[1] = A[1] + A[0] - 1;	int max = Math.max(dp[0],dp[1]);	for (int i = 2; i < A.length; i++) {		dp[i] = Math.max(dp[i - 1] - A[i - 1] + A[i] - 1, A[i] + A[i - 1] - 1);		max = Math.max(dp[i],max);	}	return max;}