Largest sum Zigzag sequence in a matrix | Java 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 program to test above
import java . io . * ; class GFG { static int MAX = 100 ; static int largestZigZagSumRec ( int mat [ ] [ ] , int i , int j , int n ) { if ( i == n - 1 ) return mat [ i ] [ j ] ; int zzs = 0 ; for ( int k = 0 ; k < n ; k ++ ) if ( k != j ) zzs = Math . max ( zzs , largestZigZagSumRec ( mat , i + 1 , k , n ) ) ; return zzs + mat [ i ] [ j ] ; } static int largestZigZag ( int mat [ ] [ ] , int n ) { int res = 0 ; for ( int j = 0 ; j < n ; j ++ ) res = Math . max ( res , largestZigZagSumRec ( mat , 0 , j , n ) ) ; return res ; } public static void main ( String [ ] args ) { int n = 3 ; int mat [ ] [ ] = { { 4 , 2 , 1 } , { 3 , 9 , 6 } , { 11 , 3 , 15 } } ; System . out . println ( " Largest ▁ zigzag ▁ sum : ▁ " + largestZigZag ( mat , n ) ) ; } }