Maximum Subarray with elimination

Question

I know how to find the maximum contiguous subarray of an array in O(n). However the 2nd problem in the following link asks to find the maximum contiguous subarray when some of the elements (k) can be eliminated: http://www.iarcs.org.in/inoi/2011/inoi2011/inoi2011-qpaper.pdf I can't seem to find an efficient way to do this.

If you understand how the contiguous-subarray solution works, you should be able to modify it ever so slightly for the contiguous-subarray-with-some-holes case. The complexity of the latter is actually O(N log K). No more hints, this figure is a dead giveaway. — n. m. could be an AI
– n. m. could be an AI, Commented Dec 31, 2012 at 15:59
after looking at your comment, the problem became very easy. Thanks for the hint — Shivam Gupta
– Shivam Gupta, Commented Dec 31, 2012 at 16:22

Ivaylo Strandjev · Accepted Answer · 2012-12-31 10:26:08Z

2

Given the constraints I believe doing a O(N^2) solution will do. I will not tell you how to solve the problem but will give you some hints:

Note that the numbers are quite limited in value - they may only be in the range [-10^4, 10^4] this makes it possible to have an array that counts how many numbers you have with a given value(in the whole array or only in a given interval)
Iterate over the lengths of the subarray you will be choosing and solve the problem for each length in linear time
Note that for a given array you will always discard the k values that are smallest OR all the negative numbers in the subarray if they are less than k

Hope this will help you to solve the problem.

answered Dec 31, 2012 at 10:26

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

nhahtdh Over a year ago

Given the constraints I believe doing a O(N^2) solution will do In the worst case, N can be 10^4 - which is a bit borderline and may not pass the time limit.

Ivaylo Strandjev Over a year ago

@nhahtdh I usually go for a N^2 solution in 2 sec time limits. Most of the online judge systems I have seen pass even with 1 billion operations or more in 2 secs. I believe this solution will be fast enough. Also please note the solution I propose is quite simple computation wise so it will really use only about 2 * 10^8 simple operations. Should do I believe.

nhahtdh Over a year ago

Fair enough if you say so - I rarely venture near the time limit myself so I don't really know.

mhsekhavat · Accepted Answer · 2012-12-31 15:14:17Z

1

there is an O(N.K) dynamic programming solution:

let d[i][j] (0<=i<=N, 0<=j<=K) be the maximum sum of any (possibly empty) sub-array ending with ith element by eliminating j elements.

initial values: d[0][j] = 0 for 0<=j<=K

updating dynamic values:

for i = 1 to N:
     d[i][0] = max (d[i-1][0]+a[i], 0)
     for j = 1 to K:
         d[i][j] = max(d[i-1][j]+a[i], d[i-1][j-1])

and solution is max{d[N][j]} for 0<=j<=K

edited Dec 31, 2012 at 15:14

answered Dec 31, 2012 at 14:12

mhsekhavat

1,02714 silver badges20 bronze badges

Collectives™ on Stack Overflow

Maximum Subarray with elimination

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related