Maximum size of subset of given array such that a triangle can be formed by any three integers as the sides of the triangle | C ++ program for the above approach ; Function to find the maximum size of the subset of the given array such that a triangle can be formed from any three integers of the subset as sides ; Sort arr [ ] in increasing order ; Stores the maximum size of a valid subset of the given array ; Stores the starting index of the current window ; Stores the last index of the current window ; Iterate over the array arr [ ] ; Increment j till the value of arr [ i ] + arr [ i + 1 ] > arr [ j ] holds true ; Update the value of maxSize ; Return Answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximizeSubset ( int arr [ ] , int N ) { sort ( arr , arr + N ) ; int maxSize = 0 ; int i = 0 ; int j = i + 2 ; while ( i < N - 2 ) { while ( arr [ i ] + arr [ i + 1 ] > arr [ j ] ) { j ++ ; } maxSize = max ( maxSize , j - i ) ; i ++ ; j = max ( j , i + 2 ) ; } return maxSize ; } int main ( ) { int arr [ ] = { 2 , 7 , 4 , 1 , 6 , 9 , 5 , 3 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximizeSubset ( arr , N ) << endl ; return 0 ; }