Tutorialspoint.dev

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.

Prerequisite: Kadane’s Algorithm

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 <bits/stdc++.h>
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

<?php
// PHP program to find out k maximum 
// non-overlapping sub-array sums.
  
    // Method to compute k 
    // maximum sub-array sums.
    function kmax($arr, $k, $n) {
      
        // In each iteration it will give
        // the ith maximum subarray sum.
        for( $c = 0; $c < $k; $c++)
        
            // Kadane's algorithm.
            $max_so_far = PHP_INT_MIN;
            $max_here = 0;
      
            // compute starting and ending
            // index of each of the sub-array.
            $start = 0; $end = 0; $s = 0;
            for($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.
            echo "Maximum non-overlapping sub-arraysum" ;
            echo ($c + 1) , ": ", $max_so_far
            echo", starting index: " , $start ;
            echo", ending index: " , $end , ".";
            echo" ";
      
            // Replace all elements of the maximum subarray 
            // by -infinity. Hence these places cannot form 
            // maximum sum subarray again.
            for ( $l = $start; $l <= $end; $l++)
                $arr[$l] = PHP_INT_MIN;
        }
        echo " ";
    }
      
    // Driver Program
        // Test case 1
        $arr1 = array(4, 1, 1, -1, -3, -5,
                            6, 2, -6, -2);
        $k1 = 3;
        $n1 = count($arr1);
          
        // Function calling
        kmax($arr1, $k1, $n1);
      
        // Test case 2
        $arr2 = array(5, 1, 2, -6, 2, -1, 3, 1);
        $k2 = 2;
        $n2 =count($arr2);
          
        // Function calling
        kmax($arr2, $k2, $n2);
  
// This code is contributed by anuj_67.
?>

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



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter