Dynamic Programming21 sections · 916 units
Open in Course

Codeforces 977F Consecutive Subsequence - Base Cases

Learn how to initialize the DP values before processing the array elements.

3. Set the base cases

You process the array from left to right, and because:

  • You have not selected any number yet.
  • No subsequence has been built yet.

So:

  • dp[v] = 0 for every possible v
  • last_pos[v] = -1 (any non-possible entry)
  • prev[i] = -1 for all i
  • best_end = -1 - It's the index where the optimal subsequence ends.
  • best_len = 0 - It's the length of the optimal subsequence ending at best_end

These initializations make sure every value starts empty before you process the first element.