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
import java . util . * ; import java . io . * ; class GFG { static int maxSubarraySum ( int arr [ ] , int N , int 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 ++ ) { cSum += arr [ i ] ; 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 ) ; if ( sit != end ) max_sum = Math . max ( max_sum , cSum - sit ) ; cum_set . add ( cSum ) ; } return max_sum ; } static int lower_bound ( ArrayList < Integer > al , int x ) { 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 ; } public static void main ( String args [ ] ) { int arr [ ] = { 5 , - 2 , 6 , 3 , - 5 } ; int K = 15 ; int N = arr . length ; System . out . println ( maxSubarraySum ( arr , N , K ) ) ; } }