两端值相同的最大区间和：按端点值维护最小前缀

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 选择i<j且a[i]=a[j]，最大化含两端的sum(a[i:j+1])；不存在返回None。
• 并非长度最长，也不是中间值全与端点相同。

解题路线

1. 记P[j+1]为截至当前值的前缀和。以x为末端时，需要同值起点i的最小P[i]，因为区间和=P[j+1]−P[i]。
2. 哈希表x→此前该值出现处的最小“包含它之前”的前缀。先查询候选再插入当前，保证i<j。
3. 允许负值意味着最早同值起点未必最优。例如前面一段累积很负，之后同值出现前的P更小，要更新最小前缀。

手动走一遍

[1,−10,1,5,1]：第一到末尾总和−2，但从第二个1到末尾和7；表需要保留P=−9而非初始0。[2,−8,2]唯一合法区间和−4，仍应返回−4而非初始化为0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def max_equal_endpoint_sum(a):
    prefix, first_min, answer = 0, {}, None
    for x in a:
        end = prefix + x
        if x in first_min:
            score = end - first_min[x]
            answer = score if answer is None else max(answer, score)
        first_min[x] = min(first_min.get(x, prefix), prefix)
        prefix = end
    return answer

复杂度

期望O(n)时间、O(d)空间，d为不同数值；哈希最坏情况和大整数位成本按语言实现考虑。

易错点与追问

容易失分的边界

• 当前起点提前插入会错误允许单元素。
• 初始化answer=0会把全负但有合法答案的输入误判。

继续深挖

• 如果要求j−i≥L，怎样延迟加入可用起点？
• 如果端点差为给定D，查询哪个键，如何处理两个方向？