NONOVSEG - Editorial

Let dp[i][j][k] denote the maximum number of segments that can be kept at their positions in the first i segments, out of which the last fixed segment was the j, and the parameter k denotes the number of segments that should be moved out, if k is negative, then it means this many number of segments should be moved in the range [0, x[j]]

This dp will require \mathcal{O}(n^3) time and space. You can optimize the space to \mathcal{O}(n^2) by storing just the last layer.