Maximum sum subarray having sum less than or equal to given sum using Set | Java 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 ; x is the target value or key ; Driver code ; Initialise the array ; Initialise the value of K ; Size of array
using System ; using System . Collections . Generic ; class GFG { static int maxSubarraySum ( int [ ] arr , int N , int 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 ++ ) { cSum += arr [ i ] ; 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 ) ; if ( sit != end ) max_sum = Math . Max ( max_sum , cSum - sit ) ; cum_set . Add ( cSum ) ; } return max_sum ; } static int lower_bound ( List < int > al , int x ) { 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 ; } public static void Main ( string [ ] args ) { int [ ] arr = { 5 , - 2 , 6 , 3 , - 5 } ; int K = 15 ; int N = arr . Length ; Console . Write ( maxSubarraySum ( arr , N , K ) ) ; } }