ENG  RUS Timus 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;

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;
}

/* 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 ?