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).