Largest sum subarray with at-least k numbers

0 0 11 minutes read

Given an array, find the subarray (containing at least k numbers) which has the largest sum.
Examples:

Input : arr[] = {-4, -2, 1, -3} 
            k = 2
Output : -1
The sub array is {-2, 1}

Input : arr[] = {1, 1, 1, 1, 1, 1} 
            k = 2
Output : 6 
The sub array is {1, 1, 1, 1, 1, 1}

Asked in : Facebook

This problem is an extension of Largest Sum Subarray Problem.

We first compute maximum sum till every index and store it in an array maxSum[].
After filling the array, we use the sliding window concept of size k. Keep track of sum of current k elements. To compute sum of current window, remove first element of previous window and add current element. After getting the sum of current window, we add the maxSum of the previous window, if it is greater than current max, then update it else not.

Below is the implementation of above approach:

C

// C code to implement the approach
 
#include <stdio.h>
 
// Function to find the maximum sum
int findMaxSum(int arr[], int N)
{
    // Declare dp array
    int dp[N][2];
    if (N == 1) {
        return arr[0];
    }
 
    // Initialize the values in dp array
    dp[0][0] = 0;
    dp[0][1] = arr[0];
 
    // Loop to find the maximum possible sum
    for (int i = 1; i < N; i++) {
        dp[i][1] = dp[i - 1][0] + arr[i];
        dp[i][0] = (dp[i - 1][1] > dp[i - 1][0])
                       ? dp[i - 1][1]
                       : dp[i - 1][0];
    }
 
    // Return the maximum sum
    return (dp[N - 1][0] > dp[N - 1][1]) ? dp[N - 1][0]
                                         : dp[N - 1][1];
}
 
// Driver Code
int main()
{
    // Creating the array
    int arr[] = { 5, 5, 10, 100, 10, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    printf("%d\n", findMaxSum(arr, N));
    return 0;
}

C++

// C++ program to find largest subarray sum with
// at-least k elements in it.
#include<bits/stdc++.h>
using namespace std;
 
// Returns maximum sum of a subarray with at-least
// k elements.
int maxSumWithK(int a[], int n, int k)
{
    // maxSum[i] is going to store maximum sum
    // till index i such that a[i] is part of the
    // sum.
    int maxSum[n];
    maxSum[0] = a[0];
 
    // We use Kadane's algorithm to fill maxSum[]
    // Below code is taken from method 3 of
    // https://www.zambiatek.com/largest-sum-contiguous-subarray/
    int curr_max = a[0];
    for (int i = 1; i < n; i++)
    {
        curr_max = max(a[i], curr_max+a[i]);
        maxSum[i] = curr_max;
    }
 
    // Sum of first k elements
    int sum = 0;
    for (int i = 0; i < k; i++)
        sum += a[i];
 
    // Use the concept of sliding window
    int result = sum;
    for (int i = k; i < n; i++)
    {
        // Compute sum of k elements ending
        // with a[i].
        sum = sum + a[i] - a[i-k];
 
        // Update result if required
        result = max(result, sum);
 
        // Include maximum sum till [i-k] also
        // if it increases overall max.
        result = max(result, sum + maxSum[i-k]);
    }
    return result;
}
 
// Driver code
int main()
{
    int a[] = {1, 2, 3, -10, -3};
    int k = 4;
    int n = sizeof(a)/sizeof(a[0]);
    cout << maxSumWithK(a, n, k);
    return 0;
}

Java

// Java program to find largest subarray sum with
// at-least k elements in it.
class Test
{
    // Returns maximum sum of a subarray with at-least
    // k elements.
    static int maxSumWithK(int a[], int n, int k)
    {
        // maxSum[i] is going to store maximum sum
        // till index i such that a[i] is part of the
        // sum.
        int maxSum[] = new int [n];
        maxSum[0] = a[0];
 
        // We use Kadane's algorithm to fill maxSum[]
        // Below code is taken from method 3 of
        // https://www.zambiatek.com/largest-sum-contiguous-subarray/
        int curr_max = a[0];
        for (int i = 1; i < n; i++)
        {
            curr_max = Math.max(a[i], curr_max+a[i]);
            maxSum[i] = curr_max;
        }
 
        // Sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += a[i];
 
        // Use the concept of sliding window
        int result = sum;
        for (int i = k; i < n; i++)
        {
            // Compute sum of k elements ending
            // with a[i].
            sum = sum + a[i] - a[i-k];
 
            // Update result if required
            result = Math.max(result, sum);
 
            // Include maximum sum till [i-k] also
            // if it increases overall max.
            result = Math.max(result, sum + maxSum[i-k]);
        }
        return result;
    }
 
    // Driver method
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, -10, -3};
        int k = 4;
        System.out.println(maxSumWithK(arr, arr.length, k));;
    }
}

Python3

# Python3 program to find largest subarray 
# sum with at-least k elements in it.
 
# Returns maximum sum of a subarray
#  with at-least k elements.
def maxSumWithK(a, n, k):
  
    # maxSum[i] is going to store 
    # maximum sum till index i such
    # that a[i] is part of the sum.
    maxSum = [0 for i in range(n)]
    maxSum[0] = a[0]
 
    # We use Kadane's algorithm to fill maxSum[]
    # Below code is taken from method3 of
    # https://www.zambiatek.com/largest-sum-contiguous-subarray/
    curr_max = a[0]
    for i in range(1, n):
     
        curr_max = max(a[i], curr_max + a[i])
        maxSum[i] = curr_max
 
    # Sum of first k elements
    sum = 0
    for i in range(k):
        sum += a[i]
 
    # Use the concept of sliding window
    result = sum
    for i in range(k, n):
     
        # Compute sum of k elements 
        # ending with a[i].
        sum = sum + a[i] - a[i-k]
 
        # Update result if required
        result = max(result, sum)
 
        # Include maximum sum till [i-k] also
        # if it increases overall max.
        result = max(result, sum + maxSum[i-k])
     
    return result
 
# Driver code
a = [1, 2, 3, -10, -3]
k = 4
n = len(a)
print(maxSumWithK(a, n, k))
 
# This code is contributed by Anant Agarwal.

C#

// C# program to find largest subarray sum with
// at-least k elements in it.
 
using System;
class Test
{
    // Returns maximum sum of a subarray with at-least
    // k elements.
    static int maxSumWithK(int[] a, int n, int k)
    {
        // maxSum[i] is going to store maximum sum
        // till index i such that a[i] is part of the
        // sum.
        int[] maxSum = new int [n];
        maxSum[0] = a[0];
  
        // We use Kadane's algorithm to fill maxSum[]
        // Below code is taken from method 3 of
        // https://www.zambiatek.com/largest-sum-contiguous-subarray/
        int curr_max = a[0];
        for (int i = 1; i < n; i++)
        {
            curr_max = Math.Max(a[i], curr_max+a[i]);
            maxSum[i] = curr_max;
        }
  
        // Sum of first k elements
        int sum = 0;
        for (int i = 0; i < k; i++)
            sum += a[i];
  
        // Use the concept of sliding window
        int result = sum;
        for (int i = k; i < n; i++)
        {
            // Compute sum of k elements ending
            // with a[i].
            sum = sum + a[i] - a[i-k];
  
            // Update result if required
            result = Math.Max(result, sum);
  
            // Include maximum sum till [i-k] also
            // if it increases overall max.
            result = Math.Max(result, sum + maxSum[i-k]);
        }
        return result;
    }
  
    // Driver method
    public static void Main()
    {
        int[] arr = {1, 2, 3, -10, -3};
        int k = 4;
        Console.Write(maxSumWithK(arr, arr.Length, k));;
    }
}

PHP

<?php
// PHP program to find largest subarray 
// sum with at-least k elements in it.
 
// Returns maximum sum of a subarray
// with at-least k elements.
function maxSumWithK($a, $n, $k)
{
     
    // maxSum[i] is going to 
    // store maximum sum till
    // index i such that a[i]
    // is part of the sum.
    $maxSum[0] = $a[0];
 
    // We use Kadane's algorithm
    // to fill maxSum[] 
    $curr_max = $a[0];
    for ($i = 1; $i < $n; $i++)
    {
        $curr_max = max($a[$i], $curr_max+$a[$i]);
        $maxSum[$i] = $curr_max;
    }
 
    // Sum of first k elements
    $sum = 0;
    for ($i = 0; $i < $k; $i++)
        $sum += $a[$i];
 
    // Use the concept of 
    // sliding window
    $result = $sum;
    for ($i = $k; $i < $n; $i++)
    {
        // Compute sum of k 
        // elements ending
        // with a[i].
        $sum = $sum + $a[$i] - $a[$i - $k];
 
        // Update result if required
        $result = max($result, $sum);
 
        // Include maximum sum till [i-k] also
        // if it increases overall max.
        $result = max($result, $sum +
                    $maxSum[$i - $k]);
    }
    return $result;
}
 
    // Driver code
    $a= array (1, 2, 3, -10, -3);
    $k = 4;
    $n = sizeof($a);
    echo maxSumWithK($a, $n, $k);
 
// This code is contributed by m_kit
?>

Javascript

<script>
    // Javascript program to find largest subarray sum with
    // at-least k elements in it.
     
    // Returns maximum sum of a subarray with at-least
    // k elements.
    function maxSumWithK(a, n, k)
    {
        // maxSum[i] is going to store maximum sum
        // till index i such that a[i] is part of the
        // sum.
        let maxSum = new Array(n);
        maxSum[0] = a[0];
    
        // We use Kadane's algorithm to fill maxSum[]
        // Below code is taken from method 3 of
        // https://www.zambiatek.com/largest-sum-contiguous-subarray/
        let curr_max = a[0];
        for (let i = 1; i < n; i++)
        {
            curr_max = Math.max(a[i], curr_max+a[i]);
            maxSum[i] = curr_max;
        }
    
        // Sum of first k elements
        let sum = 0;
        for (let i = 0; i < k; i++)
            sum += a[i];
    
        // Use the concept of sliding window
        let result = sum;
        for (let i = k; i < n; i++)
        {
            // Compute sum of k elements ending
            // with a[i].
            sum = sum + a[i] - a[i-k];
    
            // Update result if required
            result = Math.max(result, sum);
    
            // Include maximum sum till [i-k] also
            // if it increases overall max.
            result = Math.max(result, sum + maxSum[i-k]);
        }
        return result;
    }
     
    let arr = [1, 2, 3, -10, -3];
    let k = 4;
    document.write(maxSumWithK(arr, arr.length, k));
     
    // This code is contributed by rameshtravel07.
</script>

Output

-4

Time Complexity: O(n)
Auxiliary Space: O(n)

Here’s another approach:

We will first compute the sum up to k numbers and store it in the sum.
Then we will take another variable “last” and initialize with zero. This “last” variable will store sum of previous numbers.
Now loop for i = k to i<n and store the sum in “sum” variable and take j=0 and do last += arr[j] if last becomes less than zero as in Kadane’s algorithm we subtract last from sum and set last = 0 and repeats this until we reach end.

C

#include <limits.h>
#include <stdio.h>
 
long long int maxSumWithK(long long int a[],
                          long long int n, long long int k)
{
    long long int sum = 0;
    for (long long int i = 0; i < k; i++) {
        sum += a[i];
    }
 
    long long int last = 0;
    long long int j = 0;
    long long int ans = LLONG_MIN;
    ans = (ans > sum) ? ans : sum;
    for (long long int i = k; i < n; i++) {
        sum = sum + a[i];
        last = last + a[j++];
        ans = (ans > sum) ? ans : sum;
        if (last < 0) {
            sum = sum - last;
            ans = (ans > sum) ? ans : sum;
            last = 0;
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    long long int a[] = { 1, 2, 3, -10, -3 };
    long long int k = 4;
    long long int n = sizeof(a) / sizeof(a[0]);
    printf("%lld", maxSumWithK(a, n, k));
    return 0;
}

C++

#include <bits/stdc++.h>
 
using namespace std;
 
long long int maxSumWithK(long long int a[],
                          long long int n, long long int k)
{
    long long int sum = 0;
    for (long long int i = 0; i < k; i++) {
        sum += a[i];
    }
 
    long long int last = 0;
    long long int j = 0;
    long long int ans = LLONG_MIN;
    ans = max(ans, sum);
    for (long long int i = k; i < n; i++) {
        sum = sum + a[i];
        last = last + a[j++];
        ans = max(ans, sum);
        if (last < 0) {
            sum = sum - last;
            ans = max(ans, sum);
            last = 0;
        }
    }
    return ans;
}
 
// Driver code
int main()
{
    long long int a[] = { 1, 2, 3, -10, -3 };
    long long int k = 4;
    long long int n = sizeof(a) / sizeof(a[0]);
    cout << maxSumWithK(a, n, k);
    return 0;
}

Java

// Java program to implement the approach
class GFG {
 
  // function to find the largest subarray sum
  // with atleast k elements in it
  // using Kadane's algorithm
  static long maxSumWithK(long[] a, long n, int k)
  {
 
    // calculating sum of the first k elements
    // of the array
    long sum = 0;
    for (int i = 0; i < k; i++) {
      sum += a[i];
    }
 
    long last = 0;
    int j = 0;
    long ans = Long.MIN_VALUE;
    ans = Math.max(ans, sum);
 
    // iterating over the subarrays
    // and updating the sum accordingly
    for (int i = k; i < n; i += 1) {
      sum = sum + a[i];
      last = last + a[j++];
 
      // using sliding window
      // to update the ans
      ans = Math.max(ans, sum);
      if (last < 0) {
        sum = sum - last;
        ans = Math.max(ans, sum);
        last = 0;
      }
    }
    return ans;
  }
  public static void main(String[] args) {
    long[] arr = { 1, 2, 3, -10, -3 };
    int k = 4;
    long n = arr.length;
 
    // Function Call
    System.out.println(maxSumWithK(arr, n, k));
  }
}
 
// This code is contributed by phasing17

Python3

import sys
 
 
def maxSumWithK(a, n, k):
    sum = 0
    for i in range(k):
        sum += a[i]
 
    last = 0
    j = 0
    ans = -sys.maxsize - 1
    ans = max(ans, sum)
    for i in range(k, n):
        sum = sum + a[i]
        last = last + a[j]
        j += 1
        ans = max(ans, sum)
        if(last < 0):
            sum = sum-last
            ans = max(ans, sum)
            last = 0
    return ans
 
 
# Driver code
a = [1, 2, 3, -10, -3]
k = 4
n = len(a)
print(maxSumWithK(a, n, k))
 
# This code is contributed by shinjanpatra

C#

// C# program to implement the approach
 
using System;
 
public class GFG {
    // function to find the largest subarray sum
    // with atleast k elements in it
    // using Kadane's algorithm
    static long maxSumWithK(long[] a, long n, long k)
    {
        // calculating sum of the first k elements
        // of the array
        long sum = 0;
        for (long i = 0; i < k; i++) {
            sum += a[i];
        }
 
        long last = 0;
        long j = 0;
        long ans = Int64.MinValue;
        ans = Math.Max(ans, sum);
 
        // iterating over the subarrays
        // and updating the sum accordingly
        for (long i = k; i < n; i++) {
            sum = sum + a[i];
            last = last + a[j++];
 
            // using sliding window
            // to update the ans
            ans = Math.Max(ans, sum);
            if (last < 0) {
                sum = sum - last;
                ans = Math.Max(ans, sum);
                last = 0;
            }
        }
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        long[] arr = { 1, 2, 3, -10, -3 };
        long k = 4;
        long n = arr.Length;
 
        // Function Call
        Console.WriteLine(maxSumWithK(arr, n, k));
    }
}

Javascript

<script>
 
function maxSumWithK(a, n, k){
    let sum = 0
    for(let i = 0; i < k; i++)
        sum += a[i]
     
    let last = 0
    let j = 0
    let ans = Number.MIN_VALUE
    ans = Math.max(ans,sum)
    for(let i = k; i < n; i++)
    {
        sum = sum + a[i]
        last = last + a[j]
        j += 1
        ans = Math.max(ans,sum)
        if(last < 0)
        {
            sum = sum-last
            ans = Math.max(ans,sum)
            last = 0
        }
    }
    return ans
}
 
    let arr = [1, 2, 3, -10, -3];
    let k = 4;
    document.write(maxSumWithK(arr, arr.length, k));
     
// This code is contributed by shinjanpatra
 
</script>

Output

-4

Time Complexity: O(n)
Auxiliary Space: O(1)

This article is contributed by Rakesh Kumar. If you like zambiatek and would like to contribute, you can also write an article using write.zambiatek.com or mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!