Maximum sum subarray having sum less than or equal to given sum using Set | C ++ program to find maximum sum subarray less than K ; Function to maximum required sum < K ; Hash to lookup for value ( cum_sum - K ) ; getting cummulative sum from [ 0 to i ] ; lookup for upperbound of ( cSum - K ) in hash ; check if upper_bound of ( cSum - K ) exists then update max sum ; insert cummulative value in hash ; return maximum sum lesser than K ; Driver code ; initialise the array ; initialise the value of K ; size of array
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSubarraySum ( int arr [ ] , int N , int K ) { set < int > cum_set ; cum_set . insert ( 0 ) ; int max_sum = INT_MIN , cSum = 0 ; for ( int i = 0 ; i < N ; i ++ ) { cSum += arr [ i ] ; set < int > :: iterator sit = cum_set . lower_bound ( cSum - K ) ; if ( sit != cum_set . end ( ) ) max_sum = max ( max_sum , cSum - * sit ) ; cum_set . insert ( cSum ) ; } return max_sum ; } int main ( ) { int arr [ ] = { 5 , -2 , 6 , 3 , -5 } ; int K = 15 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxSubarraySum ( arr , N , K ) ; return 0 ; }