Home » Interview coding problems/challenges

# Largest zigzag sequence

**Largest zigzag sequence**: This problem is a standard recursion problem being featured in Directi. Here, we are solving the **Largest zigzag sequence using dynamic programming (C++ implementation)**.

Submitted by Radib Kar, on April 19, 2020

**Problem statement:**

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 (0^{th} 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 0^{th} 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.

**Solution Approach:**

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, cur_{row}, cur_{colulm}, n)

Function recurZigzag(matrix,cur_{row},cur_{colulm}): If (cur_{row}reaches n) Return 0; for i=0 to n except cur_{column}Return matrix[cur_{row}][cur_{column}] + max(recurZigzag(matrix, cur_{row}+ 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions