CareerCup

algorithmist dot com/index dot php/Kadane's_Algorithm

K maximum sums in a one-dimensional array
01: for k←1 to K do begin
02: min[k]←∞; M[k]←−∞;
03: end;
04: sum[0]←0; min[1]←0; M[1]←0;
05: for i←1 to n do begin
06: sum[i]←sum[i-1]+a[i];
07: for k←1 to K do cand[k]←sum[i]-min[k];
08: M←K largest elements of merge(M,cand);
09: insert sum[i] into min;
10: end

a solution from my end:
1- Store all the n(n+1)/2 possible subarrays sum in a max heap.
2- Find out the kth max subarray by k delete heap operations.
Time Complexity: O(n2)

I get to know that there is an algorithm of O(n + K) complexity. Can sb please, update me on the same (Logical steps and data structures required)

Same as maxSubSum problem with k-sized stack. Complexity O(n) + K sized extra memory

There is a paper on this, if you are interested you can read

- But the basic idea is to construct only the K heaps at a time, and find k largest sums from these heaps using a heap selection algorithm.

- Then all the heaps are deleted except the last one. And this last one is used to generate the next set of K heaps.

- Repeat the above two steps till you find out all the k sets.

e.g. 2,3,4,5,6,7,8,9
k=3 // subarray size
sum=0
max=sum;

1> take sum of first k elements (2,3,4 = 9)
max=sum;
2> for(i=k+1;i<length;i++)
2.1 sum=sum+a[i]
2.1 sum=sum-a[i-k]; // using previous sum by deleting element
2.2 if(max < sum) then max = sum
3> print max

QuickSelect

login2win.blogspot.com/2011/06/quick-select.html

If overlapping is allowed, I think we can use a generalization version of the Kadane's algorithm, which just put all the ever-computed maximum subarray sum into a k heap. As a result at the end of the traverse of the array, the heap will contain the maximum k subarray sum which is just the result. Please refer to the en.wikipedia.org/wiki/Maximum_subarray_problem

If overlapping is allowed, I think we can use a generalization version of the Kadane's algorithm, which just put all the ever-computed maximum subarray sum into a k heap. As a result at the end of the traverse of the array, the heap will contain the maximum k subarray sum which is just the result. Please refer to the en.wikipedia.org/wiki/Maximum_subarray_problem

we can use quick sort partition logic.
partition the array taking any element.
we get a partition position for that element say p.
if p is less that k, then partition p to N elements again.
else partition 1 to P elements.

keep selecting partition till you get the partition position as k. then 1 to k will be your answer.

Someone pointed this link for quick_select algo login2win.blogspot.in/2011/06/quick-select.html

I have a question here.

I am not sure if the algorithm even is working..

In the partition part,

while ( input[r] > pivot )
r--;

Is this required as pivot = input[r]; So r value never changes.

And when I executed the algo on paper, I am not even getting the result properly. Can some one verify and explain if I am missing any point here.

Virendr pawar

algorithmist dot com/index dot php Kadane's_Algorithm

kadanes algorithm