Longest Subarray with first element greater than or equal to Last element | Search function for searching the first element of the subarray which is greater or equal to the last element ( num ) ; Returns length of the longest array with first element smaller than the last element . ; Initially the search space is empty . ; We will add an ith element in the search space if the search space is empty or if the ith element is greater than the last element of the search space . ; we will search for the index first element in the search space and we will use it find the index of it in the original array . ; Update the answer if the length of the subarray is greater than the previously calculated lengths . ; Driver code
< ? php function binarySearch ( $ searchSpace , $ s , $ e , $ num ) { $ ans = 0 ; while ( $ s <= $ e ) { $ mid = ( $ s + $ e ) / 2 ; if ( $ searchSpace [ $ mid ] >= $ num ) { $ ans = $ mid ; $ e = $ mid - 1 ; } else { $ s = $ mid + 1 ; } } return $ ans ; } function longestSubArr ( & $ arr , $ n ) { $ j = 0 ; $ ans = 0 ; for ( $ i = 0 ; $ i < $ n ; ++ $ i ) { if ( $ j == 0 or $ searchSpace [ $ j - 1 ] < $ arr [ $ i ] ) { $ searchSpace [ $ j ] = $ arr [ $ i ] ; $ index [ $ j ] = $ i ; $ j ++ ; } $ idx = binarySearch ( $ searchSpace , 0 , $ j - 1 , $ arr [ $ i ] ) ; $ ans = max ( $ ans , $ i - $ index [ $ idx ] + 1 ) ; } return $ ans ; } $ arr = array ( -5 , -1 , 7 , 5 , 1 , -2 ) ; $ n = sizeof ( $ arr ) ; echo ( longestSubArr ( $ arr , $ n ) ) ; ? >