I am preparing for a national programming competition and I encountered this problem.
It is as follows : -
You are given an array of length M. You are required to select K non-intersecting subarrays. The cost will be considered as the sum of all numbers in these subarrays divided by K . Your task is to maximize this cost.
You can select no subarrays (0) and the cost(C) will be ZERO IN THAT CASE!
If there are more than one solutions that contain the same cost, then select the one that contains the highest VALUE OF K.
You have to print the value of C and K
Array consists of positive as well as negative integers.
Here is my solution :-
I used Kadane's algorithm,
to find the longest subarray and printed K as 1 and the sum. It passed a few tests though : D
How can I efficiently solve this problem?
Do I have to apply Kadane's algorithm again and again?
Example-->
Subarray : 1 2 3 4 -100 -33330 -345 1 2 3 4 5
Here,we can choose, 2 subarrays:- {1,2,3,4} and {1,2,3,4,5},
our cost will be= ((10)+(15))/2=12.5
On the other hand, if we only choose 1 subarray, then the sum is 15/1=15(which is also the cost)
So, the best way is to choose only 1 subarray in this above example-case.:-)