Max sum of M non-overlapping subarrays of size K
In this problem, we are tasked with finding the maximum sum of M non-overlapping subarrays of size K within a given array. The objective is to efficiently determine the subarrays that provide the maximum combined sum without overlapping.
Problem Statement
Given an array of integers, we need to find M non-overlapping subarrays of size K that yield the maximum sum.
Example Scenario
Consider the array:
-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10
If we want to find 3 non-overlapping subarrays of size 2 that result in the maximum sum, the subarrays are: [7, 8], [6, 5], [4, 10], with a total sum of 40.
Idea to Solve the Problem
To solve this problem, we can use dynamic programming. We start by calculating the prefix sums of the array and
storing them in the sum
array. Then, we use recursion to explore all possibilities of selecting
non-overlapping subarrays of size K. For each position, we either select the current subarray or skip it, and we
take the maximum of these two possibilities.
Pseudocode
int findMaxNonOverlapSubarray(int sum[], int start, int n, int m, int k)
{
// Base cases
if (m == 0)
return 0;
if (start > n - 1)
return 0;
// Calculate the maximum of two possibilities
return max(
sum[start] + findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
findMaxNonOverlapSubarray(sum, start + 1, n, m, k)
);
}
Algorithm Explanation
- Create a function
findMaxNonOverlapSubarray
that takes thesum
array, the starting positionstart
, the size of the arrayn
, the number of subarraysm
, and the subarray sizek
. - Implement base cases: if
m
becomes 0 (we have found all required subarrays) or ifstart
exceeds the array bounds, return 0. - For each position
start
, calculate the maximum sum by either including the current subarray's sum and recursively exploring the next non-overlapping subarray, or skipping the current subarray and moving on to the next position. - Return the maximum of the two possibilities.
Code Solution
// C Program
// Max sum of M non-overlapping subarrays of size K
#include <stdio.h>
int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
int findMaxNonOverlapSubarray(int sum[], int start, int n, int m, int k)
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return max(sum[start] + findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k), findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
void maxNonOverlapSubarray(int arr[], int n, int m, int k)
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
printf(" Given m : %d k : %d ",m,k);
// Use to store sum
int sum[(n + 1) - k];
// Set the initial zero to all sum element
for (int i = 0; i < n + 1 - k; ++i)
{
sum[i] = 0;
}
for (int i = 0; i < k; i++)
{
sum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
// Find non overlapping subarray
int result = findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
printf("\n %d\n", result);
}
int main()
{
int arr[] = {
-1 , 9 , 1 , 7 , 8 , 0 , 4 , 6 , 5 , 2 , 4 , 10
};
// Get the size of arr
int n = sizeof(arr) / sizeof(arr[0]);
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
maxNonOverlapSubarray(arr, n, 2, 3);
return 0;
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
package main
import "fmt"
/*
Go Program for
Max sum of M non-overlapping subarrays of size K
*/
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
// Find non overlapping subarrays using recursion
func findMaxNonOverlapSubarray(sum[] int, start int, n int, m int, k int) int {
if m == 0 {
return 0
}
if start > n - 1 {
return 0
}
return max(sum[start] +
findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
findMaxNonOverlapSubarray(sum, start + 1, n, m, k))
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
func maxNonOverlapSubarray(arr[] int, n int, m int, k int) {
if n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n {
// When invalid input
return
}
fmt.Print(" Given m : ", m, " k : ", k, " ")
// Use to store sum
var sum = make([]int, (n + 1) - k)
for i := 0 ; i < k ; i++ {
sum[0] += arr[i]
}
for i := 1 ; i <= n - k ; i++ {
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1]
}
// Find non overlapping subarray
var result int = findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k)
// Display result
fmt.Print("\n ", result, "\n")
}
func main() {
// Given array elements
var arr = [] int {
-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10,
}
// Get the size of arr
var n int = len(arr)
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
maxNonOverlapSubarray(arr, n, 3, 2)
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
maxNonOverlapSubarray(arr, n, 2, 3)
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
/*
Java Program for
Max sum of M non-overlapping subarrays of size K
*/
public class Subarray
{
public int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
public int findMaxNonOverlapSubarray(int[] sum, int start, int n, int m, int k)
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return max(sum[start] +
findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
public void maxNonOverlapSubarray(int[] arr, int n, int m, int k)
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
System.out.print(" Given m : " + m + " k : " + k + " ");
// Use to store sum
int[] sum = new int[(n + 1) - k];
// Set the initial zero to all sum element
for (int i = 0; i < n + 1 - k; ++i)
{
sum[i] = 0;
}
for (int i = 0; i < k; i++)
{
sum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
// Find non overlapping subarray
int result = findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
System.out.print("\n " + result + "\n");
}
public static void main(String[] args)
{
Subarray task = new Subarray();
// Given array elements
int[] arr = {
-1 , 9 , 1 , 7 , 8 , 0 , 4 , 6 , 5 , 2 , 4 , 10
};
// Get the size of arr
int n = arr.length;
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3);
}
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Max sum of M non-overlapping subarrays of size K
*/
class Subarray
{
public: int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
int findMaxNonOverlapSubarray(int sum[], int start, int n, int m, int k)
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return this->max(sum[start] +
this->findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
this->findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
void maxNonOverlapSubarray(int arr[], int n, int m, int k)
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m *k) > n)
{
// When invalid input
return;
}
cout << " Given m : " << m << " k : " << k << " ";
// Use to store sum
int sum[(n + 1) - k];
// Set the initial zero to all sum element
for (int i = 0; i < n + 1 - k; ++i)
{
sum[i] = 0;
}
for (int i = 0; i < k; i++)
{
sum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
// Find non overlapping subarray
int result = this->findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
cout << "\n " << result << "\n";
}
};
int main()
{
Subarray *task = new Subarray();
// Given array elements
int arr[] = {
-1 , 9 , 1 , 7 , 8 , 0 , 4 , 6 , 5 , 2 , 4 , 10
};
// Get the size of arr
int n = sizeof(arr) / sizeof(arr[0]);
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task->maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task->maxNonOverlapSubarray(arr, n, 2, 3);
return 0;
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
// Include namespace system
using System;
/*
Csharp Program for
Max sum of M non-overlapping subarrays of size K
*/
public class Subarray
{
public int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
public int findMaxNonOverlapSubarray(int[] sum, int start, int n, int m, int k)
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return this.max(sum[start] +
this.findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
this.findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
public void maxNonOverlapSubarray(int[] arr, int n, int m, int k)
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
Console.Write(" Given m : " + m + " k : " + k + " ");
// Use to store sum
int[] sum = new int[(n + 1) - k];
// Set the initial zero to all sum element
for (int i = 0; i < n + 1 - k; ++i)
{
sum[i] = 0;
}
for (int i = 0; i < k; i++)
{
sum[0] += arr[i];
}
for (int i = 1; i <= n - k; i++)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
// Find non overlapping subarray
int result = this.findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
Console.Write("\n " + result + "\n");
}
public static void Main(String[] args)
{
Subarray task = new Subarray();
// Given array elements
int[] arr = {
-1 , 9 , 1 , 7 , 8 , 0 , 4 , 6 , 5 , 2 , 4 , 10
};
// Get the size of arr
int n = arr.Length;
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3);
}
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
<?php
/*
Php Program for
Max sum of M non-overlapping subarrays of size K
*/
class Subarray
{
public function max($a, $b)
{
if ($a > $b)
{
return $a;
}
else
{
return $b;
}
}
// Find non overlapping subarrays using recursion
public function findMaxNonOverlapSubarray($sum, $start, $n, $m, $k)
{
if ($m == 0)
{
return 0;
}
if ($start > $n - 1)
{
return 0;
}
return $this->max($sum[$start] +
$this->findMaxNonOverlapSubarray($sum, $start + $k, $n, $m - 1, $k),
$this->findMaxNonOverlapSubarray($sum, $start + 1, $n, $m, $k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
public function maxNonOverlapSubarray($arr, $n, $m, $k)
{
if ($n == 0 || $m <= 0 || $k <= 0 || $k > $n || ($m * $k) > $n)
{
// When invalid input
return;
}
echo(" Given m : ".$m.
" k : ".$k.
" ");
// Use to store sum
$sum = array_fill(0, ($n + 1) - $k, 0);
for ($i = 0; $i < $k; $i++)
{
$sum[0] += $arr[$i];
}
for ($i = 1; $i <= $n - $k; $i++)
{
$sum[$i] += $sum[$i - 1] + $arr[$i + $k - 1] - $arr[$i - 1];
}
// Find non overlapping subarray
$result = $this->findMaxNonOverlapSubarray($sum, 0, $n + 1 - $k, $m, $k);
// Display result
echo("\n ".$result.
"\n");
}
}
function main()
{
$task = new Subarray();
// Given array elements
$arr = array(-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10);
// Get the size of arr
$n = count($arr);
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
$task->maxNonOverlapSubarray($arr, $n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
$task->maxNonOverlapSubarray($arr, $n, 2, 3);
}
main();
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
/*
Node JS Program for
Max sum of M non-overlapping subarrays of size K
*/
class Subarray
{
max(a, b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
findMaxNonOverlapSubarray(sum, start, n, m, k)
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return this.max(sum[start] +
this.findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
this.findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
maxNonOverlapSubarray(arr, n, m, k)
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
process.stdout.write(" Given m : " + m + " k : " + k + " ");
// Use to store sum
var sum = Array((n + 1) - k).fill(0);
for (var i = 0; i < k; i++)
{
sum[0] += arr[i];
}
for (var i = 1; i <= n - k; i++)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
}
// Find non overlapping subarray
var result = this.findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
process.stdout.write("\n " + result + "\n");
}
}
function main()
{
var task = new Subarray();
// Given array elements
var arr = [-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10];
// Get the size of arr
var n = arr.length;
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3);
}
main();
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
# Python 3 Program for
# Max sum of M non-overlapping subarrays of size K
class Subarray :
def max(self, a, b) :
if (a > b) :
return a
else :
return b
# Find non overlapping sublists using recursion
def findMaxNonOverlapSubarray(self, sum, start, n, m, k) :
if (m == 0) :
return 0
if (start > n - 1) :
return 0
return self.max(sum[start] +
self.findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
self.findMaxNonOverlapSubarray(sum, start + 1, n, m, k))
# k = is sublist length
# m = number of sublist
# n = size of list
# arr = given list
def maxNonOverlapSubarray(self, arr, n, m, k) :
if (n == 0 or m <= 0 or k <= 0 or k > n or(m * k) > n) :
# When invalid input
return
print(" Given m : ", m ," k : ", k ," ", end = "")
# Use to store sum
sum = [0] * ((n + 1) - k)
i = 0
while (i < k) :
sum[0] += arr[i]
i += 1
i = 1
while (i <= n - k) :
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1]
i += 1
# Find non overlapping sublist
result = self.findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k)
# Display result
print("\n ", result )
def main() :
task = Subarray()
# Given list elements
arr = [-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10]
# Get the size of arr
n = len(arr)
# Case A
# [7,8],[6,5],[4,10] length k = 2 sublist m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2)
# Case B
# [9, 1, 7],[2, 4, 10] length k = 3 sublist m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3)
if __name__ == "__main__": main()
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
# Ruby Program for
# Max sum of M non-overlapping subarrays of size K
class Subarray
def max(a, b)
if (a > b)
return a
else
return b
end
end
# Find non overlapping subarrays using recursion
def findMaxNonOverlapSubarray(sum, start, n, m, k)
if (m == 0)
return 0
end
if (start > n - 1)
return 0
end
return self.max(sum[start] +
self.findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
self.findMaxNonOverlapSubarray(sum, start + 1, n, m, k))
end
# k = is subarray length
# m = number of subarray
# n = size of array
# arr = given array
def maxNonOverlapSubarray(arr, n, m, k)
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
# When invalid input
return
end
print(" Given m : ", m ," k : ", k ," ")
# Use to store sum
sum = Array.new((n + 1) - k) {0}
i = 0
while (i < k)
sum[0] += arr[i]
i += 1
end
i = 1
while (i <= n - k)
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1]
i += 1
end
# Find non overlapping subarray
result = self.findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k)
# Display result
print("\n ", result ,"\n")
end
end
def main()
task = Subarray.new()
# Given array elements
arr = [-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10]
# Get the size of arr
n = arr.length
# Case A
# [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2)
# Case B
# [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3)
end
main()
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
/*
Scala Program for
Max sum of M non-overlapping subarrays of size K
*/
class Subarray()
{
def max(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
def findMaxNonOverlapSubarray(sum: Array[Int],
start: Int, n: Int, m: Int, k: Int): Int = {
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return max(sum(start) +
findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
def maxNonOverlapSubarray(arr: Array[Int], n: Int, m: Int, k: Int): Unit = {
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
print(" Given m : " + m + " k : " + k + " ");
// Use to store sum
var sum: Array[Int] = Array.fill[Int]((n + 1) - k)(0);
var i: Int = 0;
while (i < k)
{
sum(0) += arr(i);
i += 1;
}
i = 1;
while (i <= n - k)
{
sum(i) += sum(i - 1) + arr(i + k - 1) - arr(i - 1);
i += 1;
}
// Find non overlapping subarray
var result: Int = findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
print("\n " + result + "\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Subarray = new Subarray();
// Given array elements
var arr: Array[Int] = Array(-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10);
// Get the size of arr
var n: Int = arr.length;
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3);
}
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
import Foundation;
/*
Swift 4 Program for
Max sum of M non-overlapping subarrays of size K
*/
class Subarray
{
func max(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
func findMaxNonOverlapSubarray(_ sum: [Int],
_ start: Int, _ n: Int, _ m: Int, _ k: Int) -> Int
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return self.max(sum[start] +
self.findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
self.findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
func maxNonOverlapSubarray(_ arr: [Int], _ n: Int, _ m: Int, _ k: Int)
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
print(" Given m : ", m ," k : ", k ," ", terminator: "");
// Use to store sum
var sum = Array(repeating: 0, count: (n + 1) - k);
var i = 0;
while (i < k)
{
sum[0] += arr[i];
i += 1;
}
i = 1;
while (i <= n - k)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
i += 1;
}
// Find non overlapping subarray
let result = self.findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
print("\n ", result );
}
}
func main()
{
let task = Subarray();
// Given array elements
let arr = [-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10];
// Get the size of arr
let n = arr.count;
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3);
}
main();
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
/*
Kotlin Program for
Max sum of M non-overlapping subarrays of size K
*/
class Subarray
{
fun max(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Find non overlapping subarrays using recursion
fun findMaxNonOverlapSubarray(sum: Array < Int > ,
start: Int, n: Int, m: Int, k: Int): Int
{
if (m == 0)
{
return 0;
}
if (start > n - 1)
{
return 0;
}
return this.max(sum[start] +
this.findMaxNonOverlapSubarray(sum, start + k, n, m - 1, k),
this.findMaxNonOverlapSubarray(sum, start + 1, n, m, k));
}
/*
k = is subarray length
m = number of subarray
n = size of array
arr = given array
*/
fun maxNonOverlapSubarray(arr: Array < Int > ,
n: Int, m: Int, k: Int): Unit
{
if (n == 0 || m <= 0 || k <= 0 || k > n || (m * k) > n)
{
// When invalid input
return;
}
print(" Given m : " + m + " k : " + k + " ");
// Use to store sum
val sum: Array < Int > = Array((n + 1) - k)
{
0
};
var i: Int = 0;
while (i < k)
{
sum[0] += arr[i];
i += 1;
}
i = 1;
while (i <= n - k)
{
sum[i] += sum[i - 1] + arr[i + k - 1] - arr[i - 1];
i += 1;
}
// Find non overlapping subarray
val result: Int = this.findMaxNonOverlapSubarray(sum, 0, n + 1 - k, m, k);
// Display result
print("\n " + result + "\n");
}
}
fun main(args: Array < String > ): Unit
{
val task: Subarray = Subarray();
// Given array elements
val arr: Array < Int > = arrayOf(-1, 9, 1, 7, 8, 0, 4, 6, 5, 2, 4, 10);
// Get the size of arr
val n: Int = arr.count();
// Case A
// [7,8],[6,5],[4,10] length k = 2 subarray m = 3
task.maxNonOverlapSubarray(arr, n, 3, 2);
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
task.maxNonOverlapSubarray(arr, n, 2, 3);
}
input
Given m : 3 k : 2
40
Given m : 2 k : 3
33
Output Explanation
The code implements the algorithm and finds the maximum sum of non-overlapping subarrays based on the provided input. It demonstrates two test cases and displays the resulting maximum sums.
Time Complexity
The time complexity of this algorithm is O(n * m), where n is the size of the array and m is the number of subarrays. This is because each position is visited for each subarray, and the overlapping subproblems are memoized, resulting in efficient computation.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment