|
|
back to boardGetting wrong answer for test case #3 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 ? |
|
|