ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1146. Maximum Sum

Getting wrong answer for test case #3
Послано Aakanksha Sharma 3 сен 2019 16:44
My code is as following:
#include<iostream>
#include<vector>
using namespace std;

long getMaxSumRow(long rowArr[], int n) {
    long cs = 0;
    long ms = 0;
    bool positiveNumberPresent = false;

    for (int i = 0; i < n; i++) {
        if (!positiveNumberPresent && (rowArr[i] >= 0)) {
            positiveNumberPresent = true;
        }
        cs += rowArr[i];

        if (cs < 0) {
            cs = 0;
            continue;
        }

        if (cs > ms) {
            ms = cs;
        }
    }

    if (positiveNumberPresent) {
        return ms;
    }

    ms = rowArr[0];

    for (int i = 0; i < n; i++) {
        if (rowArr[i] > ms) {
            ms = rowArr[i];
        }
    }

    return ms;
}

long maxSumRec(vector<vector<long> > &arr, int n) {
    if (n == 1) {
        return arr[0][0];
    }

    /* Take an array for running rows sum */
    long runningRowSum[n];

    for (int r = 0; r < n; r++) {
        runningRowSum[r] = 0;
    }

    long maxSum = INT_MIN;

    /* Initialize variables for left-right and top-bottom bounds */
    int left, right, top = 0, bottom = n-1;

    /* Iterate from all possible lefts to all possibe rights ahead of this left */
    for (left = 0; left < n; left++) {
        for (right = 0; right < n; right++) {
            for (top = 0; top <= bottom; top++) {
                runningRowSum[top] += arr[top][right];
            }
            /* For this left-right combination, calculate contigeous subarray with maximum sum in runningRowSum */
            long currSum = getMaxSumRow(runningRowSum, n);

            if (currSum > maxSum) {
                maxSum = currSum;
            }
        }
        /* Reinitialize running row sum to 0 */
        for (int r = 0; r < n; r++) {
            runningRowSum[r] = 0;
        }
    }

    return maxSum;
}

int main() {
    int n;
    cin >> n;
    vector<vector<long> > arr(n);

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

    cout << maxSumRec(arr, n);
    return 0;
}

But I am getting wrong answer for test case#3 . Any advice on what it might be failing at ?