题解 | 小红的双排列删除得分

import sys
n=int(input())
a=[0]+list(map(int,input().split()))
M=0#记录最大和
start=[0]*(n+1)#存储元素a[i]的下标
S=[0]*(2*n+1)#前i个元素之和
dp=[0]*(2*n+1)#记录到i为止最高分
for i in range(1,2*n+1):
    S[i]=a[i]+S[i-1]
    #获取当前元素的开始下标
    star=start[a[i]]
    if star:
        #计算star到当前的元素和
        cur =S[i]-S[star-1]
        #可以删除多段区间
        #dp[star-1]为这个区间开始之前的最佳得分
        dp[i]=dp[star-1]+cur
    else:
        start[a[i]]=i#记录第一次出现位置
    dp[i]=max(dp[i],dp[i-1])    
print(dp[2*n])