Largest sum Zigzag sequence in a matrix | Memoization based 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 dp = [ [ 0 for i in range ( MAX ) ] for j in range ( MAX ) ] NEW_LINE def largestZigZagSumRec ( mat , i , j , n ) : NEW_LINE INDENT if ( dp [ i ] [ j ] != - 1 ) : NEW_LINE INDENT return dp [ i ] [ j ] ; NEW_LINE DEDENT if ( i == n - 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = mat [ i ] [ j ] ; NEW_LINE return ( dp [ 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 dp [ i ] [ j ] = ( zzs + mat [ i ] [ j ] ) ; NEW_LINE return ( dp [ i ] [ j ] ) ; NEW_LINE DEDENT def largestZigZag ( mat , n ) : NEW_LINE INDENT for i in range ( MAX ) : NEW_LINE INDENT for k in range ( MAX ) : NEW_LINE INDENT dp [ i ] [ k ] = - 1 ; NEW_LINE DEDENT DEDENT 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