线性dp, 设f[i]为以 i 结尾的最长连续数字子序列的长度
f[i] = f[j] + 1,其中 j 是在 i 之前,离i最近的 nums[i] - 1 的下标
将nums的元素放进一个 key 为 nums[i], value 为 nums[i] 的出现下标列表 的字典里,
每次在 这个下标列表 里二分寻找下标 j
时间复杂度O(nlogn)
python 代码
import bisect
n = int(input())
nums = list(map(int, input().split()))
mp = {}
for i, e in enumerate(nums):
if mp.get(e, None) == None:
mp[e] = []
mp[e].append(i)
ans, mx = 0, 0
f = [0] * n
for i in range(n):
f[i] = 1
lst = mp.get(nums[i] - 1, None)
if lst != None:
pre = bisect.bisect_right(lst, i)
if pre == len(lst) or lst[pre] > i: pre -= 1
if pre != -1: f[i] = f[lst[pre]] + 1
if f[i] > ans:
ans = f[i]
mx = nums[i]
idxs = []
for i in range(n - 1, -1, -1):
if mx == nums[i]:
idxs.append(i + 1)
mx -= 1
idxs = idxs[::-1]
print(len(idxs))
print(' '.join(map(str, idxs)))