Largest subset having with sum less than equal to sum of respective indices | Java program to implement the above approach ; 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
import java . util . * ; class GFG { public static int findSubset ( int [ ] a , int n ) { int sum = 0 ; int cnt = 0 ; Vector < Integer > v = new Vector < > ( ) ; for ( int i = 1 ; i <= n ; i ++ ) { if ( a [ i - 1 ] - i <= 0 ) { sum += a [ i - 1 ] - i ; cnt += 1 ; } else { v . add ( a [ i - 1 ] - i ) ; } } Collections . sort ( v ) ; int ptr = 0 ; while ( ptr < v . size ( ) && sum + v . get ( ptr ) <= 0 ) { cnt += 1 ; ptr += 1 ; sum += v . get ( ptr ) ; } return cnt ; } public static void main ( String [ ] args ) { int arr [ ] = { 4 , 1 , 6 , 7 , 8 , 2 } ; int n = arr . length ; System . out . println ( findSubset ( arr , n ) ) ; } }