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
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.
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)
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.