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 . ; Search space for the potential first elements . ; It will store the Indexes of the elements of search space in the original array . ; 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
def binarySearch ( searchSpace , s , e , num ) : NEW_LINE INDENT while ( s <= e ) : NEW_LINE INDENT mid = ( s + e ) // 2 NEW_LINE if searchSpace [ mid ] >= num : NEW_LINE INDENT ans = mid NEW_LINE e = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT s = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT def longestSubArr ( arr , n ) : NEW_LINE INDENT searchSpace = [ None ] * n NEW_LINE index = [ None ] * n NEW_LINE j = 0 NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( j == 0 or searchSpace [ j - 1 ] < arr [ i ] ) : NEW_LINE INDENT searchSpace [ j ] = arr [ i ] NEW_LINE index [ j ] = i NEW_LINE j += 1 NEW_LINE DEDENT idx = binarySearch ( searchSpace , 0 , j - 1 , arr [ i ] ) NEW_LINE ans = max ( ans , i - index [ idx ] + 1 ) NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ - 5 , - 1 , 7 , 5 , 1 , - 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( longestSubArr ( arr , n ) ) NEW_LINE DEDENT