A college professor gives several quizzes during the semester, with negative marking. He has become bored of the usual "Best $M$ out of $N$ quizzes" formula to award marks for internal assessment. Instead, each student will be evaluated based on the sum of the best contiguous segment (i.e., no gaps) of marks in the overall sequence of quizzes. However, the student is allowed to drop upto $K$ quizzes before calculating this sum.
Suppose a student has scored the following marks in $10$ quizzes during the semester.
$$\begin{array}{|c|c|c|c|c|}\hline \text{Quiz} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline \text{Marks } & 6 & -5 & 3 & -7 & 6 & -1 & 10 & -8 & -8 & 8 \\ \hline \end{array}$$
Without dropping any quizzes, the best segment is quiz $5-7$, which yields a total of $15$ marks. If the student is allowed to drop upto $2$ quizzes in a segment, the best segment is quiz $1-7$, which yields a total of $24$ marks after dropping quizzes $2$ and $4$. If the student is allowed to drop upto $6$ quizzes in a segment, the best total is obtained by taking the entire list and dropping all $5$ negative entries, yielding $33$ marks.
For $1\leq i<N, 0\leq j\leq K,$ let $B[i][j]$ denote the maximum sum segment ending at position $i$ with at most $j$ marks dropped.
- Write a recursive formula for $B[i][j].$
- Explain how to calculate, using dynamic programming, the score the professor needs to award each student.
- Describe the space and time complexity of your dynamic programming algorithm.
