Minimum Deletions for Sorted - Problem Statement

Given an array, find minimum deletions to make it sorted (non-decreasing). observation: keep the longest non-decreasing subsequence, delete the rest.

Answer = $n - \text{LIS length}$. For non-decreasing (allowing equal elements), modify LIS: use $\leq$ instead of $<$ in the comparison. Example: $[5, 3, 4, 9, 1]$. Longest non-decreasing: $[3, 4, 9]$ length $3$. Deletions: $5 - 3 = 2$. The answer is simply $n - LIS$ length. Any element not in the LIS must be removed.