Largest sum Zigzag sequence in a matrix | Python3 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
MAX = 100 NEW_LINE def largestZigZagSumRec ( mat , i , j , n ) : NEW_LINE INDENT if ( i == n - 1 ) : NEW_LINE INDENT return mat [ i ] [ j ] NEW_LINE DEDENT zzs = 0 NEW_LINE for k in range ( n ) : NEW_LINE INDENT if ( k != j ) : NEW_LINE INDENT zzs = max ( zzs , largestZigZagSumRec ( mat , i + 1 , k , n ) ) NEW_LINE DEDENT DEDENT return zzs + mat [ i ] [ j ] NEW_LINE DEDENT def largestZigZag ( mat , n ) : NEW_LINE INDENT res = 0 NEW_LINE for j in range ( n ) : NEW_LINE INDENT res = max ( res , largestZigZagSumRec ( mat , 0 , j , n ) ) NEW_LINE DEDENT return res NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 3 NEW_LINE mat = [ [ 4 , 2 , 1 ] , [ 3 , 9 , 6 ] , [ 11 , 3 , 15 ] ] NEW_LINE print ( " Largest ▁ zigzag ▁ sum : ▁ " , largestZigZag ( mat , n ) ) NEW_LINE DEDENT