LeetCode百题【最观光组合】

题目描述

解法

• 动态规划
  • 使用之前我们先看下暴力求解的思路’

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int max=-1;
        for (int i = 0; i < values.length; i++) {
			//对每个数之前的数进行遍历，找到其中符合题目要求的最大值
            for (int j = 0; j < i; j++) {
                if(values[i]+values[j]+(j-i)>max){
                    max=values[i]+values[j]-(i-j);
                }
            }
        }
        return max;
    }
}

• 由于时间复杂度过高，是过不了测试的

• 下面是动态规划的解法

• 对题目的要求我们可以换个思路

• values[i] + values[j] + i - j=values[i] +i （前面的数） + values[j] - j（当前数）

  • 也就是说，我们每次对第i个数之前的i-1个数求最大值时，value[j]-j是没有变的
  • 我们只需要求出values[i]+i的最大值就可了
  • 我们动态的维护max values[i]+i

class Solution {
    public int maxScoreSightseeingPair(int[] values) {
        int result=0;
        int maxi=values[0]+0;
        for (int i = 1; i < values.length; i++) {
            result=Math.max(result,values[i]-i+maxi);
            maxi=Math.max(maxi,values[i]+i);

        }
        return result;
    }
}

• 时间复杂度：O(n)

来源：力扣（LeetCode）
链接：1014. 最佳观光组合 - 力扣（LeetCode） (leetcode-cn.com)