Example: Sum of Elements in the ZigZag Sequence in a given Matrix in C++ using Recursion

// Sum of Elements in the ZigZag Sequence in a given Matrix in C++ using Recursion
#include <iostream>
#define MAX 100
using namespace std;

int zigZagSum(int arru[][MAX], int i, int j, int n) {
    // If we have reached bottom 
    if (i == n - 1)
        return arru[i][j];

    // This will find the largest sum in the sequence
    int zzs = 0;
    for (int k = 0; k < n; k++)
        if (k != j)
            zzs = max(zzs, zigZagSum(arru, i + 1, k, n));

    return zzs + arru[i][j];
}

int largestZigZag(int arru[][MAX], int n) {
    // This will consider all cells of top row as starting point 
    int res = 0;
    for (int j = 0; j < n; j++)
        res = max(res, zigZagSum(arru, 0, j, n));

    return res;
}

int main() {
    int n = 3;
    int arru[][MAX] = {
        {53, 33, 77, 51},
        {25, 26, 27, 28},
        {29, 20, 21, 31},
        {33, 34, 35, 36}
    };
    // arru - this variable contains the input matrix to find the largest sum

    cout << "The largest zigzag sum of the matrix is: " << largestZigZag(arru, n) << "\n";
    return 0;
}