Compute LIS values from left to right for every index
for ( i = 1 ; i < N ; i ++ ) { for ( j = 0 ; j < i ; j ++ ) { if ( arr [ i ] < arr [ j ] && lds [ i ] < lds [ j ] + 1 ) { lds [ i ] = lds [ j ] + 1 ; } } }