Largest sum Zigzag sequence in a matrix | PHP program to find the largest sum zigzag sequence ; Returns largest sum of a Zigzag sequence starting from ( i , j ) and ending at a bottom cell . ; If we have reached bottom ; Find the largest sum by considering all possible next elements in sequence . ; Returns largest possible sum of a Zizag sequence starting from top and ending at bottom . ; Consider all cells of top row as starting point ; Driver Code
< ? php $ MAX = 100 ; function largestZigZagSumRec ( $ mat , $ i , $ j , $ n ) { if ( $ i == $ n - 1 ) return $ mat [ $ i ] [ $ j ] ; $ zzs = 0 ; for ( $ k = 0 ; $ k < $ n ; $ k ++ ) if ( $ k != $ j ) $ zzs = max ( $ zzs , largestZigZagSumRec ( $ mat , $ i + 1 , $ k , $ n ) ) ; return $ zzs + $ mat [ $ i ] [ $ j ] ; } function largestZigZag ( $ mat , $ n ) { $ res = 0 ; for ( $ j = 0 ; $ j < $ n ; $ j ++ ) $ res = max ( $ res , largestZigZagSumRec ( $ mat , 0 , $ j , $ n ) ) ; return $ res ; } $ n = 3 ; $ mat = array ( array ( 4 , 2 , 1 ) , array ( 3 , 9 , 6 ) , array ( 11 , 3 , 15 ) ) ; echo " Largest ▁ zigzag ▁ sum : ▁ " , largestZigZag ( $ mat , $ n ) ; ? >