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 sumint 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 Codeint 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 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 codeint 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 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 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 codea = [1, 2, 3, -10, -3]k = 4n = 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 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 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 codeint 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 codeint 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 approachclass 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 sysdef 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 codea = [1, 2, 3, -10, -3]k = 4n = len(a)print(maxSumWithK(a, n, k))# This code is contributed by shinjanpatra |
C#
// C# program to implement the approachusing 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 neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
