Given sequence of N integers, find the longest subsequence whose elements are ordered in an increasing order. Up to k exceptions that means at most k times, the next number in the sequence is smaller than previous one. Output should be the length of the longest such subsequence. In particular the question is a variant of LIS problem where at most k exceptions (restarts) are allowed.
Constraints:
3 <= N <= 10^6
1 <= K <= max{N-1,2000}
1 <= s[i] <=10^7
Time: 3 sec
Memory: 64 MB
This can be solved in $$$\mathcal{O}(n \log^{2} n)$$$ with the aliens trick. You can see my answer to the same question at Computer Science Stackexchange: link
The answer isn't complete though, as I am not able to prove the concavity of the problem. Maybe someone else here can.
Proof by AC
We can have another DP: Let $$$Cost[i][j]$$$ be the length of LIS in the interval $$$[i, j]$$$. This problem is equivalent to partitioning an array with at most $$$k+1$$$ intervals to maximize the sum of the cost for each subarray. It is well known, that if $$$Cost[i][j]$$$ is Monge, then the DP value (hence the answer) is convex.
Let's prove that $$$Cost[a][d] + Cost[b][c] \le Cost[a][c] + Cost[b][d]$$$.
Consider a LIS from interval $$$[a, d]$$$ and $$$[b, c]$$$. We will rearrange them to form an increasing sequence in the interval $$$[a, c]$$$ and $$$[b, d]$$$. Consider a polygonal chain formed by two LIS. If there is no intersection, then we just split the LIS from $$$[a, d]$$$ to $$$[a, c], [c + 1, d]$$$ and append the latter to the LIS of $$$[b, c]$$$. Otherwise, we exchange two line segments at the intersection point.
Thus, all solutions in the interval $$$[a, d]$$$ and $$$[b, c]$$$ is contained in a solution set of $$$[a, c]$$$, $$$[b, d]$$$, and the convexity is proved.
Thanks, I added a proof to the answer. I was able to prove the concavity of Monge array partition by myself:
Consider the array partitioning problem. In it we are given values $$$cost[A][B]$$$ representing the cost of interval $$$[a, b)$$$, and wish to partition the array into intervals $$$[x_{0}, x_{1}), [x_{1}, x_{2}), \dots, x_{k}, x_{k+1})$$$ where $$$x_{0} = 0, x_{k+1} = n$$$. Let $$$DP[n][k]$$$ denote the maximum sum $$$\sum_{i = 0}^{k} cost[x_{i}][x_{i+1}]$$$. We claim that $$$DP[n][k]$$$ is concave if the costs are Monge, that is, for all $$$a \leq b \leq c \leq d$$$ we have $$$cost[a][d] + cost[b][c] \leq cost[a][c] + cost[b][d]$$$.
Note that $$$DP[n][k+2] - DP[n][k+1] \leq DP[n][k+1] - DP[n][k]$$$ is the same inequality as $$$DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$$$. Take any partitions $$$x_{0}, \dots, x_{k+3}$$$ and $$$y_{0}, \dots, y_{k+1}$$$ with sums $$$DP[n][k+2]$$$ and $$$DP[n][k]$$$ respectively. Take any $$$0 \leq i \leq k$$$ such that $$$y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$$$. Such $$$i$$$ always exists, as some interval $$$[y_{i}, y_{i+1}]$$$ must be the first such that the last $$$x$$$ before the end of the interval, $$$x_{j+2} \leq y_{i+1}$$$ has $$$j \geq i$$$, thus $$$x_{i+2} \leq x_{j+2} \leq y_{i+1}$$$ and $$$y_{i} \leq x_{i+1}$$$ as otherwise the interval $$$[y_{i-1}, y_{i}]$$$ would contain $$$x_{i+1}$$$ contradicting the minimality of $$$i$$$.
We make the partitions $$$y_{0}, \dots, y_{i}, x_{i+2}, \dots, x_{k+3}$$$ and $$$x_{0}, \dots, x_{i+1}, y_{i+1}, \dots, y_{k+1}$$$, both of length $$$k+1$$$. What is the difference in total sum? Most terms cancel, but in the sum of the original two we have $$$cost[x_{i+1}][x_{i+2}]$$$ and $$$cost[y_{i}][y_{i+1}]$$$, while in the new one we have $$$cost[y_{i}][x_{i+2}]$$$ and $$$cost[x_{i+1}][y_{i+1}]$$$. But since $$$y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$$$, by the Monge property $$$cost[y_{i}][y_{i+1}] + cost[x_{i+1}][x_{i+2}] \leq cost[y_{i}][x_{i+2}] + cost[x_{i+1}][y_{i+1}]$$$, hence the total value can only increase, and $$$DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$$$.
What is monge?
Wikipedia article
The Monge Array: An Abstraction and Its Applications
Perspectives of Monge properties in optimization