Q:

Given a square matrix of size n x n, find the 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 the same column

mahmoud2506
Save to bookmark
|
2022-05-01
|
  239 
0

Largest zigzag sequence

Given a square matrix of size n x n, find the 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 the same column.

    Input:
    First line contains an integer N denoting the size of the matrix. 
    Then in the next line are N*N space separated values of the matrix.

    Output:
    Print the required max sum.

    Constraints:
    1<=N<=100
    1<=M[][]<=1000

Example:

    Input:
    Input matrix
    3 8 2
    4 8 5
    6 9 7
    
    Output: 22
    Maximum Zigzag sequence is: 
    8->5->9
    Other sequences can be: 
    3->8->6 etc.

    Input:
    Input matrix
    3  2  1
    10 8  5 
    6  6  4
    
    Output: 18
    In the above also, the maximum zigzag sequence will be:
    2->10->6

The second example clearly shows that the greedy solution wouldn't work. Let's say we opt for greedy technique and as a measure, what we do is to extract local maximum, i.e., to extract maximum out of this row and the go-ahead to the next row and find out maximum skipping the column where we found our last maximum.

So if we follow a similar approach, let's check what we can lead to.

So, firstly, we will pick 3 out of the first row (0th row)

From the next row, we will pick 8 as we can't peek 10 due to out constraint.

And from the next row, we will pick 6 (of 0th column)

So it sums up to 3+8+6 which is 17. But it's wrong we know output would be 18. So finding local best doesn't lead to global best. Hence, greedy will not work here.

We need dynamic programing or recursion to solve.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-01
need an explanation for this answer? contact us directly to get an explanation for this answer

So, let's see what can be a recursive solution. Then, we will check for overlapping sub-problems and will gradually optimize the recursion by memorization.

Let the recursive function be, recurZigzag(matrix, currow, curcolulm, n)

    Function recurZigzag(matrix,currow,curcolulm):
        If (currow reaches n)
            Return 0;
        for i=0 to n except curcolumn
            Return  matrix[currow][curcolumn] + max(recurZigzag(matrix, currow + 1, i))
    End Function

    // In the main function
    for column=0 to n-1
    result=max⁡(result,recurZigzag(matrix,0,column)

So what we did?

We are starting from each column on the top row.

Then we are recursively checking for the next row skipping the current column. So, this checks all combinations possible.

I would recommend to create the recursion tree for example 1 and check whether you can find overlapping sub-problems. There will be a lot of overlapping problems even for smaller inputs.

So, we need to pass that overhead and we can solve that by memorization technique where we store the value of solved sub-problem in DP[][]

So, we first lookup in DP[][] whether it's already solved or not. If it's already solved then we will have some value for DP[i][j] (for subproblem, f(i,j)), Else DP[i][j] will contain the initialized value only.

This is the trick here.

Below is the full CPP implementation for understanding memorization.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int findmax(vector<int> arr, int in, int n, int* lastindex)
{
    int max = INT_MIN;
    for (int i = 0; i < n; i++) {
        if (arr[i] > max && i != in) {
            max = arr[i];
            *lastindex = i;
        }
    }
    return max;
}

int recurZigZag(vector<vector<int> > arr, int row, int col, int n, int** dp)
{
    //memoization part
    if (dp[row][col] != -1) //if already solved, no need to compute again
        return dp[row][col];

    if (row == n - 1) {
        dp[row][col] = arr[row][col];
        return arr[row][col];
    }
    int max = INT_MIN;
    for (int k = 0; k < n; k++) {
        if (k != col) {
            int t = recurZigZag(arr, row + 1, k, n, dp);
            if (max < t)
                max = t;
        }
    }
    dp[row][col] = std::max(dp[row][col], arr[row][col] + max); //store solution
    return dp[row][col];
}

int main()
{
    int t, n, item;

    cout << "Enter test case:\n";
    cin >> t;

    for (int i = 0; i < t; i++) {
        cout << "Input size of square matrix\n";
        cin >> n;

        vector<vector<int> > arr;

        cout << "Input the square matrix\n";
        for (int i = 0; i < n; i++) {
            vector<int> inn;
            for (int j = 0; j < n; j++) {
                cin >> item;
                inn.push_back(item);
            }
            arr.push_back(inn);
        }

        int** dp = (int**)(malloc(sizeof(int*) * n));

        for (int i = 0; i < n; i++) {
            dp[i] = (int*)(malloc(sizeof(int) * n));
            for (int j = 0; j < n; j++)
                dp[i][j] = -1;
        }

        int mymax = INT_MIN;

        for (int i = 0; i < n; i++) {
            int p = recurZigZag(arr, 0, i, n, dp);
            if (p > mymax)
                mymax = p;
        }

        cout << "Maximum zigzag sum: " << mymax << endl;
    }

    return 0;
}

Output

 

Enter test case:
2
Input size of square matrix 
3
Input the square matrix  
3 8 2  
4 8 5  
6 9 7  
Maximum zigzag sum: 22
Input size of square matrix 
3
Input the square matrix  
3 2 1  
10 8 5 
6 6 4  
Maximum zigzag sum: 18

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
There is a grid with size NX4 and you have only on... >>
<< Shivang is a blog writer and he is working on two ...