力扣1014-最佳观光组合

        这道题的核心是要将求values[i] + values[j] + i - j最大值，转换为求values[i]+i以及values[j]-j求最大值就比较好理解。遍历的时候只需要O(n)时间复杂度即可。

package likou;
/*
 * 最佳观光组合
 * 题干：
 * 	给你一个正整数数组 values，其中 values[i]表示第 i个观光景点的评分
 * 	且两个景点i和j间的距离为j - i
 * 	一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j
 * 		也就是景点的评分之和 减去 它们两者之间的距离
 * 	返回一对观光景点能取得的最高分
 */
public class Demo1014 {
     /*
      * 解题思路：
      * 	思路一：暴力破解，时间复杂度为O(n*n)，不推荐
      * 	思路二：求解values[i] + values[j] + i - j=values[i]+i+values[j]-j值最大
      * 		当固定i时，则要求values[j]-j最大；
      *         当固定j时，则要求values[i]+i最大；
      *         因此，当对j进行遍历时，要求values[i]+i+values[j]-j最大(用sum)，其中0<i<j
      *         	则要求value[i]+i最大(用max表示)
      *         最后返回sum
      * 		
      */    
	public int maxScoreSightseeingPair(int[] values) {
           int length = values.length;
		   int max = values[0]+0;
		   int sum = values[0]+0;
           for(int j=1;j<length;j++) {
        	  sum = Math.max(sum, max+values[j]-j);
        	  max = Math.max(max, values[j]+j); 
           }
		   return sum;
    }
	
	public static void main(String args[]) {
		Demo1014 demo = new Demo1014();
		int[] values = {8,1,5,2,6};
		System.out.println(demo.maxScoreSightseeingPair(values));
	}
	
}