1014. Best Sightseeing Pair
有一個values array
score=values[i]+values[j]+i-j，其中(i<j)
請回傳最大的score
思路:
紀錄目前最大的score
並且紀錄maxsum=max(value[i]+i、value[j]+j)
這樣到values[k]時
score=max(score,maxsum+values[k]-k)
這樣就可以得到答案了
golang code :
func maxScoreSightseeingPair(values []int) int {
maxsum := 0
ans := 0
for key, val := range values {
ans = max(ans, maxsum+val-key)
maxsum = max(maxsum, key+val)
}
return ans
}