I have learnt how to find the maximum sum subsection using Kadane’s algorithm. However, in most of the questions in competitive programming, we often have to modify the algorithm to suit our purpose. For example, how to find maximum sum subsection provided that we can drop at most k elements, etc. How should I learn to modify the algorithm. Thanka in advance!
Will you mind giving an example and provide other specifications? (Link would be better) Array contains all positive or negative elements? You need not drop any if array has only positive.
For instance, suppose that a student at the training camp and there have been ten tests, in which students marks are as follows.
In this case, without being allowed to drop any tests, the best segment is tests 5–7, which yields a total of 15 marks. If student is allowed to drop upto 2 tests in a segment, the best segment is tests 1–7, which yields a total of 24 marks after dropping tests 2 and 4. If student is allowed to drop upto 6 tests in a segment, the best total is obtained by taking the entire list and dropping the 5 negative entries to get a total of 33.
You will be given a sequence of N test marks and a number K. You have to compute the sum of the best segment in the sequence when upto K marks may be dropped from the segment. Both negative and positive marks are possible.
it is really good
really nice algorithm modification
Plz send python algorithm