Skip to main content

Max sum of M non-overlapping subarrays of size K

Here given code implementation process.

// 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
Last updated on by Kalkicode




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.

New Comment