c++ - My largest sub-square-matrix sum program is outputting the largest rectangle, not the largest square

Question

I need to Write a program that takes in a square matrix of integers and outputs the largest sub-square-matrix sum. The first line of input is an integer which indicates the dimension of the square matrix, followed by the actual matrix row-by-row.

I have a program working however, it outputs the largest sum of a rectangle and not a square which is required.

Example input:

3

1 2 3

4 5 6

-7 -8 -9

Output: Should be 16(2+3+5+6) however it is outputting 21(1+2+3+4+5+6)

Here is my code:

#include<iostream>

using namespace std;

int kadaneAlgo(int arr[], int& start, int& end, int n) 
{
    //find max sum and starting and ending location
    int sum = 0, maxSum = INT_MIN;
    end = -1;        //at first no place is selected

    int tempStart = 0;        //starting from 0

    for (int i = 0; i < n; i++) {
        sum += arr[i];

        if (sum < 0) {
            sum = 0;
            tempStart = i + 1;
        }
        else if (sum > maxSum)
        {
            //get maximum sum, and update start and end index
            maxSum = sum;
            start = tempStart;
            end = i;
        }
    }

    if (end != -1)
        return maxSum;

    //when all elements are negative in the array
    maxSum = arr[0];
    start = end = 0;

    // Find the maximum element in array
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxSum) {
            maxSum = arr[i];
            start = end = i;
        }
    }

    return maxSum;
}

void maxSqSum() 
{
    int maxSum = INT_MIN;

    int n;
    cin >> n;
    int left, right;
    int temp[n], sum, start, end;


    int mat[100][100];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> mat[i][j];
        }
    }

    for (left = 0; left < n; left++) {
        for (int i = 0; i < n; i++)//temp initially holds all 0
            temp[i] = 0;

        for (right = left; right < n; ++right)
        {
            //for each row, find the sum
            for (int i = 0; i < n; ++i)
                temp[i] += mat[i][right];

            sum = kadaneAlgo(temp, start, end, n);

            //find sum of square    
            if (sum > maxSum) {
                //find maximum value of sum, then update corner points
                maxSum = sum;
            }
        }
    }

    cout << maxSum;

}

int main() 
{
    maxSqSum();
}