Leetcode # 1014. Best Sightseeing Pair

https://leetcode.com/problems/best-sightseeing-pair/submissions/

Solution

Key Point

score(i, j) := values[i] + values[j] + i – j, i < j
不管 j 為多少，「 values[i] + i 」部分是不改變的

class Solution:  
  def maxScoreSightseeingPair(self, values: List[int]) -> int:
    best_i_so_far = 0
    max_score = values[0] + values[1] - 1
    for i in range(2, len(values)):
      score = [best_i_so_far + values[best_i_so_far], \
               i - 1 + values[i - 1]]
      best_i_so_far = best_i_so_far if score[0] > score[1] else (i -1)
      max_score = max(max_score, max(score) + values[i] - i)
      
    return max_score

Last Updated on 2023/08/16 by A1go