I have a programming assignment which I was told that is solvable with some DP algorithm. The question is a variant of LIS problem where at most $k$ exceptions (restarts) are allowed. 

But I know that there is a better solution. My professor mentioned Lagrange Multipliers and giving a penalty for each restart. But after googling these terms I wasn't able to find out anything related to algorithms. Every article is about Calculus and function optimization. 
I also read about them on Wikipedia but I can't figure out how to use them.
 
Is there a keyword that can describe better what I want to read?