Longest subsequence such that difference between adjacents is one | Function to find the length of longest subsequence ; Initialize the dp [ ] array with 1 as a single element will be of 1 length ; Start traversing the given array ; Compare with all the previous elements ; If the element is consecutive then consider this subsequence and update dp [ i ] if required . ; Longest length will be the maximum value of dp array . ; Longest subsequence with one difference is { 1 , 2 , 3 , 4 , 3 , 2 }
< ? php function longestSubseqWithDiffOne ( $ arr , $ n ) { $ dp [ $ n ] = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ dp [ $ i ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < $ i ; $ j ++ ) { if ( ( $ arr [ $ i ] == $ arr [ $ j ] + 1 ) || ( $ arr [ $ i ] == $ arr [ $ j ] - 1 ) ) $ dp [ $ i ] = max ( $ dp [ $ i ] , $ dp [ $ j ] + 1 ) ; } } $ result = 1 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( $ result < $ dp [ $ i ] ) $ result = $ dp [ $ i ] ; return $ result ; } $ arr = array ( 1 , 2 , 3 , 4 , 5 , 3 , 2 ) ; $ n = sizeof ( $ arr ) ; echo longestSubseqWithDiffOne ( $ arr , $ n ) ; ? >