# K maximum sums of non-overlapping contiguous sub-arrays

Given an Array of Integers and an Integer value k, find out k non-overlapping sub-arrays which have k maximum sums.

Examples:

```Input : arr1[] = {4, 1, 1, -1, -3, -5, 6, 2, -6, -2},
k = 3.
Output : Maximum non-overlapping sub-array sum1: 8,
starting index: 6, ending index: 7.

Maximum non-overlapping sub-array sum2: 6,
starting index: 0, ending index: 2.

Maximum non-overlapping sub-array sum3: -1,
starting index: 3, ending index: 3.

Input : arr2 = {5, 1, 2, -6, 2, -1, 3, 1},
k = 2.
Output : Maximum non-overlapping sub-array sum1: 8,
starting index: 0, ending index: 2.

Maximum non-overlapping sub-array sum2: 5,
starting index: 4, ending index: 7.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Kadane’s algorithm finds out only the maximum subarray sum, but using the same algorithm we can find out k maximum non-overlapping subarray sums. The approach is:

• Find out the maximum subarray in the array using Kadane’s algorithm. Also find out its starting and end indices. Print the sum of this subarray.
• Fill each cell of this subarray by -infinity.
• Repeat process 1 and 2 for k times.

## C++

 `// C++ program to find out k maximum  ` `// non-overlapping sub-array sums. ` `#include ` `using` `namespace` `std; ` ` `  `// Function to compute k maximum ` `// sub-array sums. ` `void` `kmax(``int` `arr[], ``int` `k, ``int` `n) { ` ` `  `    ``// In each iteration it will give ` `    ``// the ith maximum subarray sum. ` `    ``for``(``int` `c = 0; c < k; c++){ ` ` `  `        ``// Kadane's algorithm. ` `        ``int` `max_so_far = numeric_limits<``int``>::min(); ` `        ``int` `max_here = 0; ` ` `  `        ``// compute starting and ending ` `        ``// index of each of the sub-array. ` `        ``int` `start = 0, end = 0, s = 0; ` `        ``for``(``int` `i = 0; i < n; i++) ` `        ``{ ` `            ``max_here += arr[i]; ` `            ``if` `(max_so_far < max_here) ` `            ``{ ` `                ``max_so_far = max_here; ` `                ``start = s; ` `                ``end = i; ` `            ``} ` `            ``if` `(max_here < 0) ` `            ``{ ` `                ``max_here = 0; ` `                ``s = i + 1; ` `            ``} ` `        ``} ` ` `  `        ``// Print out the result. ` `        ``cout << ``"Maximum non-overlapping sub-array sum"` `             ``<< (c + 1) << ``": "``<< max_so_far  ` `             ``<< ``", starting index: "` `<< start  ` `             ``<< ``", ending index: "` `<< end << ``"."` `<< endl; ` ` `  `        ``// Replace all elements of the maximum subarray  ` `        ``// by -infinity. Hence these places cannot form  ` `        ``// maximum sum subarray again. ` `        ``for` `(``int` `l = start; l <= end; l++) ` `            ``arr[l] = numeric_limits<``int``>::min(); ` `    ``} ` `    ``cout << endl; ` `} ` ` `  `// Driver Program ` `int` `main() ` `{ ` `    ``// Test case 1 ` `    ``int` `arr1[] = {4, 1, 1, -1, -3,  ` `                 ``-5, 6, 2, -6, -2}; ` `    ``int` `k1 = 3; ` `    ``int` `n1 = ``sizeof``(arr1) / ``sizeof``(arr1[0]); ` `     `  `    ``// Function calling ` `    ``kmax(arr1, k1, n1); ` ` `  `    ``// Test case 2 ` `    ``int` `arr2[] = {5, 1, 2, -6, 2, -1, 3, 1}; ` `    ``int` `k2 = 2; ` `    ``int` `n2 = ``sizeof``(arr2)/``sizeof``(arr2[0]); ` `     `  `    ``// Function calling ` `    ``kmax(arr2, k2, n2); ` `     `  `    ``return` `0; ` `} `

## Java

 `// Java program to find out k maximum  ` `// non-overlapping sub-array sums. ` ` `  `class` `GFG { ` ` `  `    ``// Method to compute k maximum  ` `    ``// sub-array sums. ` `    ``static` `void` `kmax(``int` `arr[], ``int` `k, ``int` `n) { ` `     `  `        ``// In each iteration it will give ` `        ``// the ith maximum subarray sum. ` `        ``for``(``int` `c = ``0``; c < k; c++) ` `        ``{  ` `            ``// Kadane's algorithm. ` `            ``int` `max_so_far = Integer.MIN_VALUE; ` `            ``int` `max_here = ``0``; ` `     `  `            ``// compute starting and ending ` `            ``// index of each of the sub-array. ` `            ``int` `start = ``0``, end = ``0``, s = ``0``; ` `            ``for``(``int` `i = ``0``; i < n; i++) ` `            ``{ ` `                ``max_here += arr[i]; ` `                ``if` `(max_so_far < max_here) ` `                ``{ ` `                    ``max_so_far = max_here; ` `                    ``start = s; ` `                    ``end = i; ` `                ``} ` `                ``if` `(max_here < ``0``) ` `                    ``{ ` `                    ``max_here = ``0``; ` `                    ``s = i + ``1``; ` `                ``} ` `            ``} ` `     `  `            ``// Print out the result. ` `            ``System.out.println(``"Maximum non-overlapping sub-arraysum"` `+ ` `                                ``(c + ``1``) + ``": "` `+  max_so_far +  ` `                                ``", starting index: "` `+ start + ` `                                ``", ending index: "` `+ end + ``"."``); ` `     `  `            ``// Replace all elements of the maximum subarray  ` `            ``// by -infinity. Hence these places cannot form  ` `            ``// maximum sum subarray again. ` `            ``for` `(``int` `l = start; l <= end; l++) ` `                ``arr[l] = Integer.MIN_VALUE; ` `        ``} ` `        ``System.out.println(); ` `    ``} ` `     `  `    ``// Driver Program ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``// Test case 1 ` `        ``int` `arr1[] = {``4``, ``1``, ``1``, -``1``, -``3``, -``5``,  ` `                            ``6``, ``2``, -``6``, -``2``}; ` `        ``int` `k1 = ``3``; ` `        ``int` `n1 = arr1.length; ` `         `  `        ``// Function calling ` `        ``kmax(arr1, k1, n1); ` `     `  `        ``// Test case 2 ` `        ``int` `arr2[] = {``5``, ``1``, ``2``, -``6``, ``2``, -``1``, ``3``, ``1``}; ` `        ``int` `k2 = ``2``; ` `        ``int` `n2 = arr2.length; ` `         `  `        ``// Function calling ` `        ``kmax(arr2, k2, n2); ` `    ``} ` `} ` ` `  `// This code is contributed by Nirmal Patel `

## Python3

 `# Python program to find out k maximum  ` `# non-overlapping subarray sums. ` ` `  `# Function to compute k  ` `# maximum sub-array sums. ` `def` `kmax(arr, k, n): ` ` `  `    ``# In each iteration it will give ` `    ``# the ith maximum subarray sum. ` `    ``for` `c ``in` `range``(k): ` ` `  `        ``# Kadane's algorithm ` `        ``max_so_far ``=` `-``float``(``"inf"``) ` `        ``max_here ``=` `0` ` `  `        ``# compute starting and ending ` `        ``# index of each of the subarray ` `        ``start ``=` `0` `        ``end ``=` `0` `        ``s ``=` `0` `        ``for` `i ``in` `range``(n): ` `             `  `            ``max_here ``+``=` `arr[i] ` `            ``if` `(max_so_far < max_here): ` `                 `  `                ``max_so_far ``=` `max_here ` `                ``start ``=` `s ` `                ``end ``=` `i ` `            ``if` `(max_here < ``0``): ` `                 `  `                ``max_here ``=` `0` `                ``s ``=` `i ``+` `1` ` `  `        ``# Print out the result ` `        ``print``(``"Maximum non-overlapping sub-array sum"``, ` `               ``c ``+` `1``, ``": "``, max_so_far, ``", starting index: "``, ` `               ``start, ``", ending index: "``, end, ``"."``, sep ``=` `"") ` ` `  `        ``# Replace all elements of the maximum subarray ` `        ``# by -infinity. Hence these places cannot form  ` `        ``# maximum sum subarray again. ` `        ``for` `l ``in` `range``(start, end``+``1``): ` `            ``arr[l] ``=` `-``float``(``"inf"``) ` `    ``print``() ` ` `  `# Driver Program ` `# Test case 1 ` `arr1 ``=` `[``4``, ``1``, ``1``, ``-``1``, ``-``3``, ``-``5``, ``6``, ``2``, ``-``6``, ``-``2``] ` `k1 ``=` `3` `n1 ``=` `len``(arr1) ` ` `  `# Function calling ` `kmax(arr1, k1, n1) ` ` `  `# Test case 2 ` `arr2 ``=` `[``5``, ``1``, ``2``, ``-``6``, ``2``, ``-``1``, ``3``, ``1``] ` `k2 ``=` `2` `n2 ``=` `len``(arr2) ` ` `  `# Function calling ` `kmax(arr2, k2, n2) `

## C#

 `// C# program to find out k maximum  ` `// non-overlapping sub-array sums. ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Method to compute k  ` `    ``// maximum sub-array sums. ` `    ``static` `void` `kmax(``int` `[]arr, ``int` `k, ``int` `n) { ` `     `  `        ``// In each iteration it will give ` `        ``// the ith maximum subarray sum. ` `        ``for``(``int` `c = 0; c < k; c++) ` `        ``{  ` `            ``// Kadane's algorithm. ` `            ``int` `max_so_far = ``int``.MinValue; ` `            ``int` `max_here = 0; ` `     `  `            ``// compute starting and ending ` `            ``// index of each of the sub-array. ` `            ``int` `start = 0, end = 0, s = 0; ` `            ``for``(``int` `i = 0; i < n; i++) ` `            ``{ ` `                ``max_here += arr[i]; ` `                ``if` `(max_so_far < max_here) ` `                ``{ ` `                    ``max_so_far = max_here; ` `                    ``start = s; ` `                    ``end = i; ` `                ``} ` `                ``if` `(max_here < 0) ` `                ``{ ` `                    ``max_here = 0; ` `                    ``s = i + 1; ` `                ``} ` `            ``} ` `     `  `            ``// Print out the result. ` `            ``Console.WriteLine(``"Maximum non-overlapping sub-arraysum"` `+ ` `                              ``(c + 1) + ``": "``+ max_so_far +  ` `                              ``", starting index: "` `+ start +  ` `                              ``", ending index: "` `+ end + ``"."``); ` `     `  `            ``// Replace all elements of the maximum subarray  ` `            ``// by -infinity. Hence these places cannot form  ` `            ``// maximum sum subarray again. ` `            ``for` `(``int` `l = start; l <= end; l++) ` `                ``arr[l] = ``int``.MinValue; ` `        ``} ` `    ``Console.WriteLine(); ` `    ``} ` `     `  `    ``// Driver Program ` `    ``public` `static` `void` `Main(String[] args) ` `    ``{ ` `        ``// Test case 1 ` `        ``int` `[]arr1 = {4, 1, 1, -1, -3, -5, ` `                            ``6, 2, -6, -2}; ` `        ``int` `k1 = 3; ` `        ``int` `n1 = arr1.Length; ` `         `  `        ``// Function calling ` `        ``kmax(arr1, k1, n1); ` `     `  `        ``// Test case 2 ` `        ``int` `[]arr2 = {5, 1, 2, -6, 2, -1, 3, 1}; ` `        ``int` `k2 = 2; ` `        ``int` `n2 = arr2.Length; ` `         `  `        ``// Function calling ` `        ``kmax(arr2, k2, n2); ` `    ``} ` `} ` ` `  `// This code is contributed by parashar... `

## PHP

 ` `

Output:

```Maximum non-overlapping sub-array sum1: 8, starting index: 6, ending index: 7.
Maximum non-overlapping sub-array sum2: 6, starting index: 0, ending index: 2.
Maximum non-overlapping sub-array sum3: -1, starting index: 3, ending index: 3.

Maximum non-overlapping sub-array sum1: 8, starting index: 0, ending index: 2.
Maximum non-overlapping sub-array sum2: 5, starting index: 4, ending index: 7.
```

Time Complexity: The outer loop runs for k times and kadane’s algorithm in each iteration runs in linear time O(n). Hence the overall time complexity is O(k*n).