Моя самая большая программа суммы суб-квадратной матрицы выводит самый большой прямоугольник, а не самый большой квадрат - PullRequest
Новая
       23

Моя самая большая программа суммы суб-квадратной матрицы выводит самый большой прямоугольник, а не самый большой квадрат

1 голос
/ 14 октября 2019

Мне нужно написать программу, которая принимает квадратную матрицу целых чисел и выводит наибольшую сумму субквадратной матрицы. Первая строка ввода представляет собой целое число, которое указывает размерность квадратной матрицы, за которой следует строка за строкой фактической матрицы.

У меня работает программа, однако она выдает наибольшую сумму прямоугольника ине квадрат, который требуется.

Пример ввода:

3

1 2 3

4 5 6

-7 -8 -9

Вывод: должно быть 16 (2 + 3 + 5 + 6), но выводится 21 (1 + 2 + 3 + 4 + 5 + 6)

Вот мойкод: 

#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();
}
...