Compute LDS for all indices
for ( int i = N - 1 ; i >= 0 ; i -- ) { for ( int j = N - 1 ; j > i ; j -- ) { if ( arr [ j ] < arr [ i ] ) { if ( lds [ i ] < lds [ j ] + 1 ) lds [ i ] = lds [ j ] + 1 ; } } }