Codeforces 977F Consecutive Subsequence - Implementation

Input: n
Input: a[1.n]
dp = empty map (default 0) // map needed: values can be large
last_pos = empty map
for i from 1 to n:
prev[i] = -1
best_len = 0
best_end = -1
for i from 1 to n:
x = a[i]
len_i = dp[x - 1] + 1
if dp[x - 1] > 0:
prev[i] = last_pos[x - 1]
else:
prev[i] = -1
if len_i > dp[x]:
dp[x] = len_i
last_pos[x] = i
if dp[x] > best_len:
best_len = dp[x]
best_end = i
sequence_indices = empty list
p = best_end
while p != -1:
append p to sequence_indices
p = prev[p]

$dp[x]$ = best length ending at value x. Each new $a[i] = x$ extends $dp[x - 1]$. $prev[i]$ lets us reconstruct one optimal subsequence finally.

Time: $O(n)$.

Space complexity: $O(n)$ using hash map for lookups.