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
• Go
• Java
• C++
• C#
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

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

 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);
    }
}

 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;
}

 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);
	}
}

 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();

 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();

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

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

 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);
	}
}

 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();

 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);
}

 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.