Posted on by Kalkicode
Code Recursion

# 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

1. Create a function findMaxNonOverlapSubarray that takes the sum array, the starting position start, the size of the array n, the number of subarrays m, and the subarray size k.
2. Implement base cases: if m becomes 0 (we have found all required subarrays) or if start exceeds the array bounds, return 0.
3. 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.
4. 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.

## Comment

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.

Categories
Relative Post