can anyone give me a detailed explanation about the recurrence relation involved in solving this question? I tried my best but couldn’t understand the editorial.
Find the answer for segments of size <=m. Then merge the segments and find the optimal answer.
Why size less than m?-- This way the ceil value will always be 1 and you have to subtract the value of k only once from the sum of subarray.
Recurrence relation:
Ex: A = {1,2,3,-5,6,7,8}, k=3 , m =3;
You are at index 5 (consider 1 base indexing)
You can take maximum of size 3 as m is 3
What is the best possible answer, think?? because in every case you have to subtract k only.
So the answer is maximum sum subarray - k.
Now you have find the answer for size <= m . How to cover for size>m
Simply do, dp [i] = d[i-m] + sum of subarray (from index i-m+1 to i ) - k;
find the maximum of all dp[i] and this is the answer.
Implementation can be done easily by taking two variables cur and best where cur store the sum of subarray and best the maximum sum of subarray
1 Like