leetcode1014-最佳观光组合

原题

给定正整数数组 AA[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

提示:

  1. 2 <= A.length <= 50000
  2. 1 <= A[i] <= 1000

解法

思想

A[i] + A[j] + i - j可以视作A[i] + i+A[j] - j

那么可以一次遍历,用一个变量max,记录遍历中出现的最大的A[i] + i,并与遍历过程中出现的A[j] - j相加,比较出A[i] + i+A[j] - j的最大值。

代码

class Solution {
    public int maxScoreSightseeingPair(int[] A) {
        int ans = 0;
        int max = A[0] + 0;
        for (int j = 1; j < A.length; j++) {
            ans = Math.max(ans, max + A[j] - j);
            max = Math.max(max, A[j] + j);
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode1014-%e6%9c%80%e4%bd%b3%e8%a7%82%e5%85%89%e7%bb%84%e5%90%88/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年6月16日
下一篇 2020年6月18日

相关推荐

  • leetcode373-查找和最小的K对数字

    原题 给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。 定义一对值 (u,v),其中第一个元素来自 nums1,第二个元素来自 nums2。 找到和最…

    算法 2020年2月13日
    0160
  • 程序员面试金典17.01-不用加号的加法

    原题(来源Leetcode) 设计一个函数把两个数字相加。不得使用 + 或者其他算术运算符。 示例: 输入: a = 1, b = 1 输出: 2 提示: a, b 均可能是负数或…

    算法 2020年6月9日
    0590
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0220
  • leetcode134-加油站

    原题 在一条环路上有 N 个加油站,其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车,从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[…

    算法 2020年2月16日
    080
  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0120
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode100-相同的树

    原题 给定两个二叉树,编写一个函数来检验它们是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: 1 1 / \ / \ 2 3 2 …

    算法 2020年5月7日
    0210
  • leetcode387-字符串中的第一个唯一字符

    原题 给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。 案例: s = "leetcode" 返回 0. s = "loveleetcode"…

    算法 2019年12月22日
    0130
  • leetcode25-K个一组翻转链表

    原题 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原…

    算法 2020年5月9日
    0540
  • leetcode706-设计哈希映射

    原题 不使用任何内建的哈希表库设计一个哈希映射 具体地说,你的设计应该包含以下的功能 put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更…

    算法 2019年12月18日
    0120

发表回复

登录后才能评论