Maximize value of a pair from two given arrays based on given conditions | Java program for the above approach ; Class to store the values of a [ i ] , b [ i ] , a [ i ] + b [ i ] ; Constructor ; Sort values according to array ; Stores the segment tree ; Function to find the maximum possible value according to the given condition ; Initialize triplet array ; Store the values a [ i ] , b [ i ] , a [ i ] + b [ i ] ; Sort the array according to array a [ ] ; Build segment tree ; Initialise the maxvalue of the selected pairs ; Traverse the array ; For each value find the floor ( arr [ i ] + k ) ; Find the maximum value of the select pairs i and max from ( i + 1 , right ) ; Print the maximum value ; Function to search floor of the current value ; Initialise low and high values ; Perform Binary Search ; If the current value is <= val then store the candidate answer and find for rightmost one ; Function to build segment tree ; Base Case ; Build the left and right segment trees ; Update current index ; Function to get maximum value in the range [ qs , qe ] ; If segment is not in range ; If segment is completely inside the query ; Calculate the maximum value in left and right half ; Driver Code ; Function call
import java . util . * ; class triplet implements Comparable < triplet > { int a , b , c ; triplet ( int a , int b , int c ) { this . a = a ; this . b = b ; this . c = c ; } public int compareTo ( triplet o ) { return this . a - o . a ; } } class GFG { static int seg [ ] ; public static void maxValue ( int a [ ] , int b [ ] , int n , int k ) { triplet arr [ ] = new triplet [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = new triplet ( a [ i ] , b [ i ] , a [ i ] + b [ i ] ) ; } Arrays . sort ( arr ) ; seg = new int [ 4 * n ] ; build ( arr , 0 , 0 , n - 1 ) ; int maxvalue = Integer . MIN_VALUE ; for ( int i = 0 ; i < n ; i ++ ) { int right = search ( arr , arr [ i ] . a + k ) ; if ( right != - 1 ) { maxvalue = Math . max ( maxvalue , arr [ i ] . b - arr [ i ] . a + getMax ( arr , 0 , 0 , n - 1 , i + 1 , right ) ) ; } } System . out . println ( maxvalue ) ; } public static int search ( triplet arr [ ] , int val ) { int low = 0 , high = arr . length - 1 ; int ans = - 1 ; while ( low <= high ) { int mid = low + ( high - low ) / 2 ; if ( arr [ mid ] . a <= val ) { ans = mid ; low = mid + 1 ; } else high = mid - 1 ; } return ans ; } public static void build ( triplet arr [ ] , int index , int s , int e ) { if ( s == e ) { seg [ index ] = arr [ s ] . c ; return ; } int mid = s + ( e - s ) / 2 ; build ( arr , 2 * index + 1 , s , mid ) ; build ( arr , 2 * index + 2 , mid + 1 , e ) ; seg [ index ] = Math . max ( seg [ 2 * index + 1 ] , seg [ 2 * index + 2 ] ) ; } public static int getMax ( triplet arr [ ] , int index , int s , int e , int qs , int qe ) { if ( qe < s e < qs ) return Integer . MIN_VALUE / 2 ; if ( s >= qs && e <= qe ) return seg [ index ] ; int mid = s + ( e - s ) / 2 ; return Math . max ( getMax ( arr , 2 * index + 1 , s , mid , qs , qe ) , getMax ( arr , 2 * index + 2 , mid + 1 , e , qs , qe ) ) ; } public static void main ( String args [ ] ) { int N = 4 , K = 1 ; int A [ ] = { 5 , 6 , 9 , 10 } ; int B [ ] = { 3 , 0 , 10 , - 10 } ; maxValue ( A , B , N , K ) ; } }