Problem: 1272D - Remove One Element

My Solution:108781615

Hello all,

My idea: if two elements are in strictly increasing order(i.e a[I] < a[I+1] ) dp[I+1] = dp[I] + 1

else check if a[I-1] < a[I+1] then dp[I+1] = dp[I-1] + 1

I am not sure where this is going wrong. Any help is appreciated. Thanks for your time.

Auto comment: topic has been updated by levi.ackerman1732 (previous revision, new revision, compare).You should also save another state to indicate whether you have already used up your ability to delete an element or not. Something like:

$$$dp[i+1][b]=dp[i][b]+1$$$, for $$$b\in \{0,1\}$$$, if $$$a[i]<a[i+1]$$$

$$$dp[i+1][1]=dp[i-1][0]+1$$$, if $$$a[i-1]<a[i+1]$$$

return $$$max(dp[n][0],dp[n][1])$$$