Largest sum Zigzag sequence in a matrix - GeeksforGeeks
Given a matrix of size n x n, find sum of the Zigzag sequence with the largest sum. A zigzag sequence starts from the top and ends at the bottom. Two consecutive elements of sequence cannot belong to same column.
Read full article from Largest sum Zigzag sequence in a matrix - GeeksforGeeks
Given a matrix of size n x n, find sum of the Zigzag sequence with the largest sum. A zigzag sequence starts from the top and ends at the bottom. Two consecutive elements of sequence cannot belong to same column.
This problem has Optimal Substructure.
Maximum Zigzag sum starting from arr[i][j] to a
bottom cell can be written as :
zzs(i, j) = arr[i][j] + max(zzs(i+1, k)),
where k = 0, 1, 2 and k != j
zzs(i, j) = arr[i][j], if i = n-1
We have to find the largest among all as
Result = zzs(0, j) where 0 <= j < n
int largestZigZagSumRec(int mat[][MAX], int i, int j, int n){ // If we have reached bottom if (i == n-1) return mat[i][j]; // Find the largest sum by considering all // possible next elements in sequence. int zzs = 0; for (int k=0; k<n; k++) if (k != j) zzs = max(zzs, largestZigZagSumRec(mat, i+1, k, n)); return zzs + mat[i][j];}// Returns largest possible sum of a Zizag sequence// starting from top and ending at bottom.int largestZigZag(int mat[][MAX], int n){ // Consider all cells of top row as starting point int res = 0; for (int j=0; j<n; j++) res = max(res, largestZigZagSumRec(mat, 0, j, n)); return res;}int largestZigZagSumRec(int mat[][MAX], int i, int j, int n){ if (dp[i][j] != -1) return dp[i][j]; // If we have reached bottom if (i == n-1) return (dp[i][j] = mat[i][j]); // Find the largest sum by considering all // possible next elements in sequence. int zzs = 0; for (int k=0; k<n; k++) if (k != j) zzs = max(zzs, largestZigZagSumRec(mat, i+1, k, n)); return (dp[i][j] = (zzs + mat[i][j]));}// Returns largest possible sum of a Zizag sequence// starting from top and ending at bottom.int largestZigZag(int mat[][MAX], int n){ memset(dp, -1, sizeof(dp)); // Consider all cells of top row as starting point int res = 0; for (int j=0; j<n; j++) res = max(res, largestZigZagSumRec(mat, 0, j, n)); return res;}