Hello Everyone,
Given an Array of Integers and an Integer value k, find out k non-overlapping sub-arrays which have k maximum sums.
Examples:
Input : arr1[] = {4, 1, 1, -1, -3, -5, 6, 2, -6, -2},
k = 3.
Output : Maximum non-overlapping sub-array sum1: 8,
starting index: 6, ending index: 7.
Maximum non-overlapping sub-array sum2: 6,
starting index: 0, ending index: 2.
Maximum non-overlapping sub-array sum3: -1,
starting index: 3, ending index: 3.
Input : arr2 = {5, 1, 2, -6, 2, -1, 3, 1},
k = 2.
Output : Maximum non-overlapping sub-array sum1: 8,
starting index: 0, ending index: 2.
Maximum non-overlapping sub-array sum2: 5,
starting index: 4, ending index: 7.
Now,
Kadane’s algorithm finds out only the maximum subarray sum, but using the same algorithm we can find out k maximum non-overlapping subarray sums. The approach is:
- Find out the maximum subarray in the array using Kadane’s algorithm. Also find out its starting and end indices. Print the sum of this subarray.
- Fill each cell of this subarray by -infinity.
- Repeat process 1 and 2 for k times.
// C++ program to find out k maximum
// non-overlapping sub-array sums.
#include <bits/stdc++.h>
using namespace std;
// Function to compute k maximum
// sub-array sums.
void kmax( int arr[], int k, int n) {
// In each iteration it will give
// the ith maximum subarray sum.
for ( int c = 0; c < k; c++){
// Kadane's algorithm.
int max_so_far = numeric_limits< int >::min();
int max_here = 0;
// compute starting and ending
// index of each of the sub-array.
int start = 0, end = 0, s = 0;
for ( int i = 0; i < n; i++)
{
max_here += arr[i];
if (max_so_far < max_here)
{
max_so_far = max_here;
start = s;
end = i;
}
if (max_here < 0)
{
max_here = 0;
s = i + 1;
}
}
// Print out the result.
cout << "Maximum non-overlapping sub-array sum"
<< (c + 1) << ": " << max_so_far
<< ", starting index: " << start
<< ", ending index: " << end << "." << endl;
// Replace all elements of the maximum subarray
// by -infinity. Hence these places cannot form
// maximum sum subarray again.
for ( int l = start; l <= end; l++)
arr[l] = numeric_limits< int >::min();
}
cout << endl;
}
// Driver Program
int main()
{
// Test case 1
int arr1[] = {4, 1, 1, -1, -3,
-5, 6, 2, -6, -2};
int k1 = 3;
int n1 = sizeof (arr1) / sizeof (arr1[0]);
// Function calling
kmax(arr1, k1, n1);
// Test case 2
int arr2[] = {5, 1, 2, -6, 2, -1, 3, 1};
int k2 = 2;
int n2 = sizeof (arr2)/ sizeof (arr2[0]);
// Function calling
kmax(arr2, k2, n2);
return 0;
}
Output:
Maximum non-overlapping sub-array sum1: 8, starting index: 6, ending index: 7. Maximum non-overlapping sub-array sum2: 6, starting index: 0, ending index: 2. Maximum non-overlapping sub-array sum3: -1, starting index: 3, ending index: 3. Maximum non-overlapping sub-array sum1: 8, starting index: 0, ending index: 2. Maximum non-overlapping sub-array sum2: 5, starting index: 4, ending index: 7.
Time Complexity: The outer loop runs for k times and kadane’s algorithm in each iteration runs in linear time O(n). Hence the overall time complexity is O(k*n).