Compute LDS from every index in bottom up manner
for ( $ i = 1 ; $ i < $ n ; $ i ++ ) for ( $ j = 0 ; $ j < $ i ; $ j ++ ) if ( $ arr [ $ i ] < $ arr [ $ j ] and $ lds [ $ i ] < $ lds [ $ j ] + 1 ) { $ lds [ $ i ] = $ lds [ $ j ] + 1 ; }