Last Updated: 23 Apr, 2021
Largest Zigzag Sequence
Moderate
Asked in companies
You are given a matrix ‘MAT’ of dimensions ‘N x N’. Let’s define a sequence to be ‘zigzag’ if it starts from the top and ends at the bottom such that no two consecutive elements of the sequence belong to the same column.
Your task is to find the sum of the zigzag sequence with the largest sum.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains a single positive integer, ‘N’, as described in the problem statement.
The next ‘N’ lines of each test case contains ‘N’ space-separated number, ‘MAT[i][j]’, representing the value at index (i,j) of the matrix.
Output Format :
For each test case, print the “sum of the zigzag sequence with the largest sum”, as described in the problem statement.
Output for each test case will be printed in a separate line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 100
1 <= MAT[i][j] <= 1000
Where 'MAT[i][j]' denotes the value of matrix at 'jth' column of 'ith' row.
Time Limit: 1sec
Approaches
- The idea here is to find all possible zigzag sequences with the help of recursion.
- Let say we are currently at (i, j). Now we want to move to the (i+1)th row. We can go to any column that means we have total N options available in that row.
- By the definition of zigzag sequence, no two consecutive elements belong to the same column. In other words, if we are at (i, j) we can go to (i+1, k) provided k != j.
- At each iteration, we keep track of the maximum value of that function call.
- The base condition of this recursive function is when i == N-1 (i.e., the last row). So, we just return the matrix entry at (i, j).
- If you look closely at ‘approach 1’, there are repeated subproblems. How to handle these kinds of problems? Yes, you are right!. We have to use Dynamic Programming.
- We can store the result of each function call in some new array, and if we encounter a repeated subproblem, then simply return the previously saved result. This technique is known as memoization.
Steps:
- Create a 2D array named memo of the data type int, to store the result of the function calls, i.e., int memo[N+1][N+1], and ‘N’ can go up to ‘100’, so our memo will become memo[101][101]. Here, ‘memo[i][j]’ implies that we are at (i, j) then what would be the maximum value after that.
- Initialize the memo array with -1.
- Declare a variable ans = 0.
- Lets define a function solve(i, j, N, MAT), where i is the current row, j is the current column, N is the number of rows and columns in the matrix, and MAT is the given matrix.
- Run a loop from i = 0 to i < N, in each iteration do:
- ans = max(ans, solve(0, i, N, MAT)).
- Return the ans.
int solve(int i, int j, int N ,int** MAT):
- If i == N-1, return MAT[i][j].
- If we have already solved the current function call, i.e., if memo[i][j] != -1, then return the stored value.
- Declare a variable current = 0.
- Now, run a loop from k = 0 to k < N, in each iteration do:
- If k == j, then continue.
- current = max(current, MAT[i][j] + solve(i+1, k, N, MAT)).
- return memo[i][j] = current.
Similar problems