Maximum sum subarray having sum less than given sum using Set
Given an array arr[] of length N and an integer K, the task is the find the maximum sum subarray with a sum less than K.
Note: If K is less than the minimum element, then return INT_MIN.
Examples:
Input: arr[] = {-1, 2, 2}, K = 4
Output: 3
Explanation:
The subarray with maximum sum which is less than 4 is {-1, 2, 2}.
The subarray {2, 2} has maximum sum = 4, but it is not less than 4.Input: arr[] = {5, -2, 6, 3, -5}, K =15
Output: 12
Explanation:
The subarray with maximum sum which is less than 15 is {5, -2, 6, 3}.
Efficient Approach: Sum of subarray [i, j] is given by cumulative sum till j – cumulative sum till i of the array. Now the problem reduces to finding two indexes i and j, such that i < j and cum[j] – cum[i] are as close to K but lesser than it.
To solve this, iterate the array from left to right. Put the cumulative sum of i values that you have encountered till now into a set. When you are processing cum[j] what you need to retrieve from the set is the smallest number in the set which is bigger than or equal to cum[j] – K. This can be done in O(logN) using upper_bound on the set.
Below is the implementation of the above approach:
C++
// C++ program to find maximum sum // subarray less than K #include <bits/stdc++.h> using namespace std; // Function to maximum required sum < K int maxSubarraySum( int arr[], int N, int K) { // Hash to lookup for value (cum_sum - K) set< int > cum_set; cum_set.insert(0); int max_sum = INT_MIN, cSum = 0; for ( int i = 0; i < N; i++) { // getting cumulative sum from [0 to i] cSum += arr[i]; // lookup for upperbound // of (cSum-K) in hash set< int >::iterator sit = cum_set.upper_bound(cSum - K); // check if upper_bound // of (cSum-K) exists // then update max sum if (sit != cum_set.end()) max_sum = max(max_sum, cSum - *sit); // insert cumulative value in hash cum_set.insert(cSum); } // return maximum sum // lesser than K return max_sum; } // Driver code int main() { // initialise the array int arr[] = { 5, -2, 6, 3, -5 }; // initialise the value of K int K = 15; // size of array int N = sizeof (arr) / sizeof (arr[0]); cout << maxSubarraySum(arr, N, K); return 0; } |
Java
// Java program to find maximum sum // subarray less than K import java.util.*; import java.io.*; class GFG{ // Function to maximum required sum < K static int maxSubarraySum( int arr[], int N, int K) { // Hash to lookup for value (cum_sum - K) Set<Integer> cum_set = new HashSet<>(); cum_set.add( 0 ); int max_sum =Integer.MIN_VALUE, cSum = 0 ; for ( int i = 0 ; i < N; i++) { // Getting cumulative sum from [0 to i] cSum += arr[i]; // Lookup for upperbound // of (cSum-K) in hash ArrayList<Integer> al = new ArrayList<>(); Iterator<Integer> it = cum_set.iterator(); int end = 0 ; while (it.hasNext()) { end = it.next(); al.add(end); } Collections.sort(al); int sit = lower_bound(al, cSum - K); // Check if upper_bound // of (cSum-K) exists // then update max sum if (sit != end) max_sum = Math.max(max_sum, cSum - sit); // Insert cumulative value in hash cum_set.add(cSum); } // Return maximum sum // lesser than K return max_sum; } static int lower_bound(ArrayList<Integer> al, int x) { // x is the target value or key int l = - 1 , r = al.size(); while (l + 1 < r) { int m = (l + r) >>> 1 ; if (al.get(m) >= x) r = m; else l = m; } return r; } // Driver code public static void main(String args[]) { // Initialise the array int arr[] = { 5 , - 2 , 6 , 3 , - 5 }; // Initialise the value of K int K = 15 ; // Size of array int N = arr.length; System.out.println(maxSubarraySum(arr, N, K)); } } // This code is contributed by jyoti369 |
Python3
import bisect # Function to maximum required sum < K def maxSubarraySum(arr, N, K): # Hash to lookup for value (cum_sum - K) cum_set = set () cum_set.add( 0 ) max_sum = float ( '-inf' ) cSum = 0 for i in range (N): # getting cumulative sum from [0 to i] cSum + = arr[i] # lookup for upperbound of (cSum-K) in hash al = [x for x in cum_set] al.sort() lower_bound_index = bisect.bisect_left(al, cSum - K) # check if upper_bound of (cSum-K) exists then update max sum if lower_bound_index ! = len (al): max_sum = max (max_sum, cSum - al[lower_bound_index]) # // insert cumulative value in hash cum_set.add(cSum) # return maximum sum lesser than K return max_sum arr = [ 5 , - 2 , 6 , 3 , - 5 ] K = 15 N = len (arr) print (maxSubarraySum(arr, N, K)) |
C#
// Java program to find maximum sum // subarray less than K using System; using System.Collections.Generic; class GFG { // Function to maximum required sum < K static int maxSubarraySum( int [] arr, int N, int K) { // Hash to lookup for value (cum_sum - K) HashSet< int > cum_set = new HashSet< int >(); cum_set.Add(0); int max_sum = Int32.MinValue, cSum = 0; for ( int i = 0; i < N; i++) { // Getting cumulative sum from [0 to i] cSum += arr[i]; // Lookup for upperbound // of (cSum-K) in hash List< int > al = new List< int >(); int end = 0; foreach ( int it in cum_set) { end = it; al.Add(it); } al.Sort(); int sit = lower_bound(al, cSum - K); // Check if upper_bound // of (cSum-K) exists // then update max sum if (sit != end) max_sum = Math.Max(max_sum, cSum - al.ElementAt(sit)); // Insert cumulative value in hash cum_set.Add(cSum); } // Return maximum sum // lesser than K return max_sum; } static int lower_bound(List< int > al, int x) { // x is the target value or key int l = -1, r = al.Count; while (l + 1 < r) { int m = (l + r) >> 1; if (al[m] >= x) r = m; else l = m; } return r; } // Driver code public static void Main( string [] args) { // Initialise the array int [] arr = { 5, -2, 6, 3, -5 }; // Initialise the value of K int K = 15; // Size of array int N = arr.Length; Console.Write(maxSubarraySum(arr, N, K)); } } // This code is contributed by chitranayal. |
Javascript
<script> // JavaScript program to find maximum sum // subarray less than K // Function to maximum required sum < K function maxSubarraySum(arr, N, K) { // Hash to lookup for value (cum_sum - K) let cum_set = new Set(); cum_set.add(0); let max_sum = Number.MIN_SAFE_INTEGER; let cSum = 0; for (let i = 0; i < N; i++){ // Getting cumulative sum from [0 to i] cSum += arr[i]; // Lookup for upperbound // of (cSum-K) in hash let al = []; let end = 0; for (let it of cum_set) { end = it; al.push(it); } al.sort((a, b) => a - b); let sit = lower_bound(al, cSum - K); // Check if upper_bound // of (cSum-K) exists // then update max sum if (sit != end) max_sum = Math.max(max_sum, cSum - sit); // Insert cumulative value in hash cum_set.add(cSum); } // Return maximum sum // lesser than K return max_sum; } let lower_bound = (al, x) => al.filter((item) => item > x )[0] // Driver code // Initialise the array let arr = [ 5, -2, 6, 3, -5 ]; // Initialise the value of K let K = 15; // Size of array let N = arr.length; document.write(maxSubarraySum(arr, N, K)); // This code is contributed by _saurabh_jaiswal </script> |
12
Time Complexity: O(N*Log(N)), where N represents the size of the given array.
Auxiliary Space: O(N), where N represents the size of the given array.
Similar article: Maximum sum subarray having sum less than or equal to given sum using Sliding Window