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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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:

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

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

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 }