Split

For a binary string $S$, define $f(S) = $ longest non-decreasing subsequence of $S$. For example, $f(0011) = 4$ and $f(0101) = 3$. You are given a binary string $S$ of length $N$, and an integer $K$. Consider splitting $S$ into $K$ substrings, $T_1, T_2, \ldots, T_K$ such that $S = T_1 + T_2 + \ldots + T_K$. The score of such a split is defined as $\min(f(T_1), f(T_2), \ldots, f(T_K))$. Find