• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1014.最佳观光组合|BestSightseeingPair

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10587905.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

Note:

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

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

Runtime: 404 ms
Memory Usage: 19.7 MB
 1 class Solution {
 2     func maxScoreSightseeingPair(_ A: [Int]) -> Int {
 3         var n:Int = A.count
 4         var best:Int = -Int.max
 5         var most:Int = -Int.max
 6         for i in 0..<n
 7         {
 8             best = max(best, A[i] - i + most)
 9             most = max(most, A[i] + i)
10         }
11         return best       
12     }
13 }

404ms
 1 class Solution {
 2     func maxScoreSightseeingPair(_ A: [Int]) -> Int {
 3         var maxScore = Int.min
 4         var leftHighScoreIndex = 0
 5         var leftHighScoreValue = A[leftHighScoreIndex]
 6         for i in 1..<A.count {
 7             maxScore = max(leftHighScoreValue + A[i] + leftHighScoreIndex - i, maxScore)
 8             if (A[i] - leftHighScoreValue) + (i - leftHighScoreIndex) >= 0 {
 9                 leftHighScoreIndex = i 
10                 leftHighScoreValue = A[i]
11             }
12         }
13         return maxScore
14     }
15 }

440ms

 1 class Solution {
 2     func maxScoreSightseeingPair(_ A: [Int]) -> Int {
 3         // B: store max of A[0]+0 ~ A[i]+i
 4         var B = A, currMax = B[0] + 0
 5         for i in 0..<B.count {
 6             currMax = max(B[i] + i, currMax)
 7             B[i] = currMax
 8         }
 9         
10         var dp = A.map { _ in 0 }
11         for i in 1..<dp.count {
12             dp[i] = max(dp[i-1], A[i] - i + B[i-1])
13         }
14         
15         return dp.last!
16     }
17 }

460ms

 1 class Solution {
 2     func maxScoreSightseeingPair(_ A: [Int]) -> Int {
 3         var score = 0
 4         
 5         var s1 = Array<Int>()
 6         s1.reserveCapacity(A.count)
 7       
 8         for i in 0..<A.count {
 9             s1.append(A[i] + i)
10         }
11         
12         var m = Array<Int>()
13         m.append(A.last! - (A.count - 1))
14         
15         for i in (1..<A.count) {
16            m.append(max(A[A.count - i - 1] - (A.count - i - 1), m[i - 1]))
17         }
18         m.reverse()
19       
20         for i in 0..<(A.count-1) {
21             score = max(score, s1[i] + m[i + 1])
22         }
23         
24         
25         return score
26     }
27 }

464ms

 1 class Solution {
 2     func maxScoreSightseeingPair(_ A: [Int]) -> Int {
 3         var tmp = Int.min, result = Int.min
 4         for (offset, element) in A.enumerated() {
 5             result = max(result, element - offset + tmp)
 6             tmp = max(element + offset, tmp)
 7         }
 8         
 9         return result
10     }
11 }

524ms

 1 class Solution {
 2     func maxScoreSightseeingPair(_ A: [Int]) -> Int {
 3         if A.count < 2 { return -1 }        
 4         var cache = [Int]()        
 5         cache.append(0)        
 6         var res = Int.min        
 7         for idx in 1 ..< A.count {            
 8             res = max(res, A[cache.last!] + A[idx] + cache.last! - idx)
 9             if A[idx] - cache.last! + idx > A[cache.last!] {
10                 cache.append(idx)
11             }
12         }        
13         return res        
14     }
15 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap