#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/1d-dp/consecutive-subsequence-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/1d-dp/consecutive-subsequence-implementation

Repovive

Codeforces 977F Consecutive Subsequence - Implementation - 1D DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Codeforces 977F Consecutive Subsequence - Implementation

Putting it all together

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.