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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Starter code: class Solution:
    def maxScoreSightseeingPair(self, A: List[int]) -> int:
        

Solutions:
class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		curmaxsight = A[0] - 1
		curmaxpair = 0
		for sight in A[1:]:
			if sight + curmaxsight > curmaxpair:
				curmaxpair = sight + curmaxsight
			if sight > curmaxsight:
				curmaxsight = sight
			curmaxsight -= 1
		return curmaxpair


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		result = 0
		current = A[0]
		current_pos = 0
		for i in range(1, len(A)):
			value = current + A[i] + current_pos - i
			if value > result:
				result = value
			if current <= A[i] + i - current_pos:
				current = A[i]
				current_pos = i
		return result


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		res = 0
		m = A[0]
		for j in range(1, len(A)):
			res = max(res, A[j] - j + m)
			m = max(m, A[j] + j)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		ans = -math.inf
		best = -math.inf
		for (i, a) in enumerate(A):
			ans = max(ans, best + a - i)
			best = max(best, a + i)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		i = 0
		ans = float('-inf')
		for j in range(1, len(A)):
			ans = max(ans, A[i] + A[j] + i - j)
			if A[j] + j >= A[i] + i:
				i = j
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		i = 0
		max_degree = A[i] + i
		max_score = -float('inf')
		for j in range(1, len(A)):
			curr_max_score = A[j] - j + max_degree
			max_score = max(max_score, curr_max_score)
			max_degree = max(max_degree, A[j] + j)
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		B = [A[i] + i for i in range(len(A))]
		C = [A[i] - i for i in range(len(A))]
		p = 0
		q = 1
		max_score = float('-inf')
		while q < len(B):
			if B[q - 1] > B[p]:
				p = q - 1
			max_score = max(max_score, B[p] + C[q])
			q += 1
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		sA = sorted(enumerate(A), key=lambda x: x[1], reverse=True)
		L = len(A)
		maxScore = -L
		theDis = -1
		for i in range(L - 1):
			if sA[i][1] + sA[i + 1][1] <= maxScore + 1:
				break
			for j in range(i + 1, L):
				curScore = sA[i][1] + sA[j][1]
				if curScore <= maxScore + 1:
					break
				curDis = abs(sA[i][0] - sA[j][0])
				curScore -= curDis
				if curScore > maxScore:
					maxScore = curScore
					theDis = curDis
		return maxScore


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		res = imax = 0
		for (i, a) in enumerate(A):
			res = max(res, imax + A[i] - i)
			imax = max(imax, A[i] + i)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		maxI = A[0]
		ans = A[0] + A[1] - 1
		for i in range(1, len(A)):
			if ans < maxI + A[i] - i:
				ans = maxI + A[i] - i
			if maxI < A[i] + i:
				maxI = A[i] + i
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		i_sum = []
		j_sum = []
		prev = -float('inf')
		max_sum = -float('inf')
		for i in reversed(list(range(len(A)))):
			if i > 0:
				if A[i] - i > prev:
					j_sum.append(A[i] - i)
					prev = A[i] - i
				else:
					j_sum.append(prev)
			i_sum.append(A[i] + i)
		for i in reversed(list(range(1, len(i_sum)))):
			max_sum = max(max_sum, i_sum[i] + j_sum[i - 1])
		return max_sum


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		res = maxx = 0
		for i in range(len(A)):
			res = max(res, maxx + A[i])
			maxx = max(maxx, A[i]) - 1
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		max_i = 0
		score_max_i_j = []
		for j in range(len(A)):
			score_max_i_j.append(max_i + A[j] - j)
			max_i = max(max_i, A[j] + j)
		return max(score_max_i_j)


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		(a, b, n) = (0, 1, len(A))

		def opt(i, j):
			return A[i] + A[j] + i - j
		ans = [A[0], opt(0, 1)] + [0 for _ in range(n - 2)]
		for i in range(2, n):
			(opt_a, opt_b) = (opt(a, i), opt(b, i))
			if opt_a > opt_b:
				ans[i] = opt_a
				b = i
			else:
				ans[i] = opt_b
				a = b
				b = i
		return max(ans)


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		i = A[0]
		max_ans = 0
		for j in range(1, len(A)):
			x = A[j]
			print(x)
			max_ans = max(max_ans, i + x - j)
			i = max(i, x + j)
		return max_ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		preMax = A[0]
		ans = 0
		for (i, a) in enumerate(A[1:], 1):
			ans = max(ans, a - i + preMax)
			preMax = max(preMax, a + i)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		best_of_prev = A[0] - 1
		maximum = 0
		for spot in A[1:]:
			if spot + best_of_prev > maximum:
				maximum = spot + best_of_prev
			if spot > best_of_prev:
				best_of_prev = spot
			best_of_prev -= 1
		return maximum


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		best = 0
		i = 0
		for j in range(1, len(A)):
			s1 = A[i] + A[j] + i - j
			s2 = A[j] + A[j - 1] + j - 1 - j
			if s2 > s1:
				i = j - 1
			best = max(best, s1, s2)
		return best


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		lmax = A[0]
		gmax = float('-inf')
		for i in range(1, len(A)):
			cur = lmax + A[i] - i
			lmax = max(lmax, A[i] + i)
			gmax = max(gmax, cur)
		return gmax


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		(lag, lead) = (0, 1)
		prev_max_score = A[0]
		prev_max_idx = 0
		max_score = 0
		for i in range(1, len(A)):
			score = prev_max_score + A[i] - (i - prev_max_idx)
			max_score = max(score, max_score)
			if A[i] >= score - A[i]:
				prev_max_idx = i
				prev_max_score = A[i]
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		best_i = 0
		res = 0
		for (i, v) in enumerate(A):
			res = max(res, v - i + best_i)
			best_i = max(best_i, v + i)
		return res
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		d = 0
		m = A[0]
		for i in range(1, len(A)):
			d = max(d, A[i - 1] + (i - 1))
			m = max(A[i] - i + d, m)
		return m


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		n = len(A)
		pre = A[0] + 0
		res = 0
		for i in range(1, n):
			res = res if res > pre + A[i] - i else pre + A[i] - i
			pre = pre if pre > A[i] + i else A[i] + i
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		n = len(A)
		res = max_i = -n
		for j in range(1, n):
			max_i = max(max_i, A[j - 1] + j - 1)
			res = max(res, max_i + A[j] - j)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		idx = [0]
		for i in range(1, len(A)):
			if A[i] + i - idx[-1] > A[idx[-1]]:
				idx.append(i)
		res = float('-inf')
		i = 1
		j = 0
		while i < len(A):
			if j + 1 < len(idx) and idx[j + 1] < i:
				j += 1
			res = max(res, A[i] + A[idx[j]] + idx[j] - i)
			i += 1
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		arr = [A[0] + A[j] - j for j in range(1, len(A))]
		print(arr)
		maxdiff = 0
		ans = max(arr)
		for j in range(1, len(arr)):
			maxdiff = max(maxdiff, A[j] - A[0] + j)
			ans = max(ans, arr[j] + maxdiff)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		max_score = 0
		prev = ans = -float('inf')
		for i in range(1, len(A)):
			prev = max(prev, A[i - 1] + i - 1)
			ans = max(ans, prev + A[i] - i)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		i_sum = [0] * len(A)
		j_sum = [0] * len(A)
		for i in range(len(A)):
			i_sum[i] = A[i] + i
		i_sum[-1] = 0
		for j in range(len(A)):
			j_sum[j] = A[j] - j
		print(j_sum)
		prefix_sum = [-float('inf')] * len(A)
		for j in range(len(A) - 2, -1, -1):
			prefix_sum[j] = max(j_sum[j + 1], prefix_sum[j + 1])
		max_sum = -float('inf')
		for i in range(len(A)):
			max_sum = max(max_sum, prefix_sum[i] + i_sum[i])
		print(prefix_sum)
		return max_sum


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		n = len(A)
		dp = 0
		ans = 0
		for j in range(0, n):
			ans = max(ans, A[j] - j + dp)
			dp = max(dp, A[j] + j)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		(cur, ans) = (0, 0)
		for a in A:
			ans = max(ans, cur + a)
			cur = max(cur, a) - 1
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		dp_i = [0 for i in range(len(A))]
		dp_j = [0 for i in range(len(A))]
		dp_i[0] = A[0]
		dp_j[-1] = A[-1] - (len(A) - 1)
		for i in range(1, len(A)):
			dp_i[i] = max(A[i] + i, dp_i[i - 1])
		for j in range(len(A) - 2, -1, -1):
			dp_j[j] = max(A[j] - j, dp_j[j + 1])
		max_sum = 0
		for i in range(len(A) - 1):
			max_sum = max(max_sum, dp_i[i] + dp_j[i + 1])
		return max_sum


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		total = 0
		n = len(A)
		if n <= 2:
			return sum(A) - 1
		a_1 = [a + i for (i, a) in enumerate(A)]
		a_2 = [a - j for (j, a) in enumerate(A)]
		dp2 = [a for a in a_2]
		for i in range(n - 2, -1, -1):
			dp2[i] = max(dp2[i + 1], a_2[i + 1])
		dp1 = [a for a in a_1]
		dp1[0] += dp2[0]
		for i in range(1, n - 1):
			dp1[i] = max(a_1[i] + dp2[i], dp1[i - 1])
		return dp1[-2]


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		point = (A[0], 0)
		best_val = A[0]
		best_ind = 0
		max_score = 0
		for ind in range(1, len(A)):
			max_score = max(max_score, best_val + A[ind] + best_ind - ind)
			if A[ind] + ind - best_ind >= best_val:
				best_val = A[ind]
				best_ind = ind
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		d = A[1] + A[0] - 1
		m = A[0]
		for j in range(1, len(A)):
			if m + A[j] - j > d:
				d = m + A[j] - j
			if A[j] + j >= m:
				m = A[j] + j
		return d


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		if len(A) <= 1:
			return 0
		max_A_plus_i = max(A[0], A[1] + 1)
		max_score = A[0] + A[1] - 1
		for i in range(2, len(A)):
			max_score = max(max_score, max_A_plus_i + A[i] - i)
			max_A_plus_i = max(max_A_plus_i, A[i] + i)
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		res = 0
		keep = (A[0], 0)
		for j in range(1, len(A)):
			res = max(res, keep[0] + A[j] + keep[1] - j)
			if A[j] >= keep[0] or keep[0] - A[j] < j - keep[1]:
				keep = (A[j], j)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		st = []
		ret = 0
		for (i, s) in enumerate(A):
			while len(st) > 0 and st[-1][0] < s:
				(s_j, j) = st.pop()
				ret = max(ret, s + s_j - abs(i - j))
			if len(st) > 0:
				ret = max(ret, s + st[-1][0] - abs(st[-1][1] - i))
			st.append((s, i))
		return ret


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		maxa = [x + i for (i, x) in enumerate(A)]
		for i in range(1, len(maxa)):
			maxa[i] = max(maxa[i], maxa[i - 1])
		res = float('-inf')
		for j in range(1, len(A)):
			res = max(res, A[j] - j + maxa[j - 1])
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		m = -float('inf')
		res = -float('inf')
		for i in range(len(A) - 1, -1, -1):
			res = max(res, A[i] + i + m)
			m = max(m, A[i] - i)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		N = len(A)
		max_ = 0
		prev = A[-1] - N + 1
		for i in range(N - 2, -1, -1):
			max_ = max(max_, prev + A[i] + i)
			prev = max(prev, A[i] - i)
		return max_


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		res = float('-inf')
		maxleft = float('-inf')
		for (i, a) in enumerate(A):
			res = max(res, maxleft + a - i)
			maxleft = max(maxleft, a + i)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		_max_left = A[0]
		_max = 0
		for j in range(1, len(A)):
			_max = max(_max_left + A[j] - j, _max)
			_max_left = max(_max_left, A[j] + j)
		return _max


class Solution:

	def maxScoreSightseeingPair(self, a: List[int]) -> int:
		d = []
		for i in range(len(a) - 1, -1, -1):
			if i != 0:
				d.append([a[i] - i, i])
		d.sort()
		s = 0
		for i in range(0, len(a) - 1):
			while d[-1][1] <= i:
				d.pop()
			s = max(s, a[i] + i + d[-1][0])
		return s


import heapq
import math

class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		h = []
		ans = -math.inf
		for (i, a) in enumerate(A):
			if h:
				ans = max(ans, a - i - h[0])
			heapq.heappush(h, -i - a)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		A_left = [a + i for (i, a) in enumerate(A)]
		A_right = [a - i for (i, a) in enumerate(A)]
		_max_left = A_left[0]
		_max = 0
		for j in range(1, len(A_right)):
			_max = max(_max_left + A_right[j], _max)
			_max_left = max(_max_left, A_left[j])
		return _max


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		left = 0
		res = 0
		max_pre = 0
		curr_res = 0
		for right in range(1, len(A)):
			max_pre = max(max_pre, A[right - 1] + (right - 1))
			curr_res = max_pre + A[right] - right
			res = max(res, curr_res)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		(res, leftmax, cnt) = (0, 0, 0)
		for num in A:
			res = max(res, num + leftmax - cnt)
			if num > leftmax - cnt:
				leftmax = num
				cnt = 0
			cnt += 1
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		ans = 0
		best = A[0] - 1
		for i in range(1, len(A)):
			ans = max(ans, A[i] + best)
			best = max(best - 1, A[i] - 1)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		K = A[0]
		best = float('-inf')
		for j in range(1, len(A)):
			x = A[j]
			best = max(best, K + x - j)
			K = max(K, x + j)
		return best


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		max_score = 0
		scores = [0] * len(A)
		for i in range(1, len(A)):
			if i == 1:
				scores[i] = A[0] - (len(A) - (i - 1))
			else:
				scores[i] = max(A[i - 1] - (len(A) - (i - 1)), scores[i - 1])
		for j in range(1, len(A)):
			adj_score = len(A) - j + scores[j] + A[j]
			if adj_score > max_score:
				max_score = adj_score
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		m = p = 0
		for (i, n) in enumerate(A):
			m = max(m, p + n - i)
			p = max(p, n + i)
		return m


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		left = [i + a for (i, a) in enumerate(A)]
		right = [b - j for (j, b) in enumerate(A)]
		for i in range(1, len(left)):
			left[i] = max(left[i], left[i - 1])
		for i in range(len(right) - 1)[::-1]:
			right[i] = max(right[i], right[i + 1])
		return max((l + r for (l, r) in zip(left[:-1], right[1:])))


import heapq

class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		return solution(A)

def solution(A):
	right_heap = [(-(a - i), a, i) for (i, a) in enumerate(A)]
	heapq.heapify(right_heap)
	current_max = -1
	for i in range(len(A) - 1):
		right_max_score = -1
		while len(right_heap) > 0 and right_heap[0][2] <= i:
			heapq.heappop(right_heap)
		el = right_heap[0]
		right_max_score = A[i] + el[1] - abs(el[2] - i)
		current_max = max(right_max_score, current_max)
	return current_max


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		return self.with_sort(A)

	def with_sort(self, A):
		n = len(A)
		max_list = [(i[0] + i[1], i[0]) for i in sorted(enumerate(A), key=lambda x: -(x[1] + x[0] * 1.000000001))]
		idx = 0
		max_s = 0
		for j in range(n - 1, -1, -1):
			s = A[j] - j
			while idx < n and max_list[idx][1] >= j:
				idx += 1
			if idx < n:
				s += max_list[idx][0]
			max_s = max(max_s, s)
		return max_s

	def count_sort(self, A):
		C = [[] for _ in range(51001)]
		for (i, a) in enumerate(A):
			C[a + i].append((a + i, i))
		res = []
		k = 0
		for c in C:
			if len(c) > 0:
				res.extend(c)
		return list(reversed(res))

	def brute_force(self, A):
		max_score = 0
		n = len(A)
		for i in range(n):
			for j in range(i + 1, n):
				s = A[i] + A[j] + i - j
				if s > max_score:
					max_score = s
		return max_score


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		if len(A) < 2:
			return -1
		best_so_far = A[0] + 0
		res = 0
		for j in range(1, len(A)):
			res = max(res, best_so_far + A[j] - j)
			if best_so_far < A[j] + j:
				best_so_far = A[j] + j
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		if len(A) <= 1:
			return -float('inf')
		candidate = max(A[0], A[1] + 1)
		res = A[0] + A[1] - 1
		for i in range(2, len(A)):
			res = max(res, candidate + A[i] - i)
			candidate = max(candidate, A[i] + i)
		return res


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		import sys
		val = A[0] + 0
		ans = -sys.maxsize
		A.pop(0)
		for (i, num) in enumerate(A):
			ans = max(ans, val + A[i] - i - 1)
			val = max(val, A[i] + i + 1)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		if not A:
			return 0
		temp = A[0]
		ans = -999
		for i in range(1, len(A)):
			ans = max(ans, temp + A[i] - i)
			temp = max(temp, A[i] + i)
		return ans


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		largest = 0
		i = 0
		while i < len(A) - 1:
			largest = max(largest, A[i] + A[i + 1] - 1)
			if A[i] > A[i + 1]:
				(A[i], A[i + 1]) = (A[i + 1] + 1, A[i] - 1)
			i += 1
		return largest


class Solution:

	def maxScoreSightseeingPair(self, A: List[int]) -> int:
		i = 0
		res = 0
		for j in range(1, len(A)):
			ti = A[i] + i
			res = max(A[j] - j + ti, res)
			if A[j] + j > ti:
				i = j
		return res