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;
}