# 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)
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}
}``````

#### 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()
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
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)
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}
}``````

#### 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()
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}
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()
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}
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() :
#  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
#  Case B
#  [9, 1, 7],[2, 4, 10] length k = 3 sublist m = 2

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()
#  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
#  Case B
#  [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}
}``````

#### 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()
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}
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
{
// 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
// Case B
// [9, 1, 7],[2, 4, 10] length k = 3 subarray m = 2
}``````

#### input

`````` Given m : 3 k : 2
40
Given m : 2 k : 3
33``````

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