查找子数组的第一个和最后一个值相等的最大连续子数组总和

Question

有人问我这个问题，我只能想出蛮力方法

Example - [1 9 -2 9 4 2 4]
Ans - [9 -2 9] = 16
Example - [9 -18 9 2 9]
Ans - 9+2+9 = 20
Example - [5,1,4,1,10,1,7]
Ans - 1+4+1+10+1 = 17

Answer 1

我们可以使用Kadane的算法，但我们需要添加子数组和，而不是单个值。我们可以记录每个值的最佳起始指数。Python代码：

def f(A):
# Prefix sums
ps = [0] * (len(A) + 1)
for i in range(len(A)):
ps[i] = A[i] + ps[i-1]
# Map of value to its
# best starting index.
h = {}
# Best overall sum
best_sum = 0
for i in range(len(A)):
# We extend the interval by keeping the same
# starting index; Otherwise, reset the starting
# index.
if (not A[i] in h) or (ps[i] - ps[h[A[i]] - 1] <= 0):
h[A[i]] = i
candidate = ps[i] - ps[h[A[i]] - 1] if i != h[A[i]] else 0
best_sum = max(best_sum, candidate)

return best_sum
As = [
[1, 9, -2, 9, 4, 2, 4], # 16
[9, -18, 9, 2, 9], # 20
[5, 1, 4, 1, 10, 1, 7], # 17
[1, 2, 3] # 0
]
for A in As:
print(A)
print(f(A))
print('')