Largest subset having with sum less than equal to sum of respective indices | Function to find the length of the longest subset ; Stores the sum of differences between elements and their respective index ; Stores the size of the subset ; Iterate over the array ; If an element which is smaller than or equal to its index is encountered ; Increase count and sum ; Store the difference with index of the remaining elements ; Sort the differences in increasing order ; Include the differences while sum remains positive or ; Return the size ; Driver code ; Function calling
def findSubset ( a , n ) : NEW_LINE INDENT sum = 0 NEW_LINE cnt = 0 NEW_LINE v = [ ] NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( a [ i - 1 ] - i <= 0 ) : NEW_LINE INDENT sum += a [ i - 1 ] - i NEW_LINE cnt += 1 NEW_LINE DEDENT else : NEW_LINE INDENT v . append ( a [ i - 1 ] - i ) NEW_LINE DEDENT DEDENT v . sort ( ) NEW_LINE ptr = 0 NEW_LINE while ( ptr < len ( v ) and sum + v [ ptr ] <= 0 ) : NEW_LINE INDENT cnt += 1 NEW_LINE ptr += 1 NEW_LINE sum += v [ ptr ] NEW_LINE DEDENT return cnt NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 4 , 1 , 6 , 7 , 8 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( findSubset ( arr , n ) ) NEW_LINE DEDENT