Problem Statement -
The task is to find the most profitable contiguous segment of tests, given a sequence of test scores, with being allowed to drop any k tests from a chosen range.
The problem appears to be a DP problem at the outset, but complexity arises when the test drop condition comes into the picture.
What modifications can be made to the classic DP approach for this problem? Or is there a completely different approach to it?
Test Range - N <= 104
Source - INOI 2011 Q Paper