Page 3 Page 2 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector <vector <int>> a(n, vector <int> (n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } int ans = a[0][0]; for (int leng = 1; leng <= n; leng++){ for (int up = 0; up <= n-leng; up++){ vector <long long> sumv(n); for (int j = 0; j < n; j++) { for (int i = up; i < up + leng; i++) { sumv[j] += a[i][j]; } } int sum = 0; for (int r = 0; r < n; ++r) { sum += sumv[r]; ans = max(ans, sum); sum = max(sum, 0); } } } cout << ans; } 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 ? I can't understand how to solve the problem with Python and meet time limitations. I implemented solution with creating 3-D list of subsumes[column][row_start][row_offset] using accumulate from itertools and list comprehension. After that I used Kadane's algorithm. I expect that it works with O(N^3). But it isn't enough... Are there some tricks in the problem for Python? Except for stdin of course. Please, give me some tests! Solution looks like bruteforce with a precalc, not a dynamic programming one. Or precalc counts as DP? Or DP is just a clever bruteforce? Edited by author 25.07.2017 20:10 Are you calculating something like "maximal sum subarray" ? That is where it is DP. If you are doing Kadane algorithm You are doing essentially that thing dp[i] = max(0, dp[i-1] + matrix [i]) answer = max(dp[i]) My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason? #include <iostream> using namespace std; const int M = 107; int mat[M][M][M][M]; int main() { int n; cin >> n; int arr[n][n]; int ans = -1e9; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { cin >> arr[i][j]; mat[i][j][i][j] = arr[i][j]; if (arr[i][j] > ans) ans = arr[i][j]; } for (int size = 2; size<=n*n; size++) { for (int p=1; p<=size and p<=n; p++) { int q = size/p; if (p*q != size) continue; for (int i=0; i<n-p+1; i++) { for (int j=0; j<n-q+1; j++) { int x1 = i, y1 = j; int x2 = i+p-1, y2 = j+q-1; if (x2-x1 > y2-y1) { mat[x1][y1][x2][y2] = mat[x1][y1][x2-1][y2] + mat[x2][y1][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } else { mat[x1][y1][x2][y2] = mat[x1][y1][x2][y2-1] + mat[x1][y2][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } } } } } cout << ans << endl; } Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:07 Actually, if you don't access your global allocated memory, that memory don't counts. I have noticed that when watching how my solutions are testing. When there is a global array of big size first few cases are low memory. And last test cases are high memory usage. You can find any simple task were you are to output some string. Allocate a HUGE buffer for that string. Then submit your solution. Then allocate a buffer just enough to hold your string and submit again. And you will see that memory usage is the SAME. There a[i][j] in [-127..127] and n <= 100 -- May be there bitmask tricks, or other tricks???? There's one hard solution with quick matrix multiply #include <iostream> using namespace std; int n,A[1002],i,maxi,S[1002],st,dr,rez; int main() { cin>>n; for(i=1;i<=n;i++) cin>>A[i]; S[1]=A[1]; for(i=1;i<=n;i++) if(S[i-1]<=0) S[i]=A[i]; else S[i]=A[i]+S[i-1]; rez=-1000000; for(i=1;i<=n;i++) if(S[i]>rez) rez=S[i]; cout<<rez; return 0; } it's just a joke, isn't it? please help me if you have O(n^2) algorithm for this problem . thanks From my knowledge i know there is possible only O(n^3) Also accepted O(n^4) in Go 0.312 As task marked easy, it was lazy for me to implement O(n^3) oh i found my mistake Edited by author 03.11.2014 12:28 4 -1 -2 -3 -4 -5 0 -7 -8 -9 -1 -127 -100 -3 -4 -7 -1 I have WA on tc 4 too and am unable to figure it out. Some help? Firstly my solution got TLE#4. Next, I make mew solution with new idea, and got WA#4. Also, my 2nd solution makes mistake in this test: 4 0 -2 -1 0 9 2 -9 -2 -4 1 -1 1 -1 8 10 -2 answer is 18. It can help someone. P.S. forry for bad English. I haven't idea how to approach this test? my code is simple O(n^4),but #9 test doesn' work: for (i=1;i<=n;i++) { for (j=1;j<=n;j++)
s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1];
} for (i=1;i<=n;i++) for (j=1;j<=n;j++) { for (k=i;k<=n;k++) { for (m=j;m<=n;m++) { sum=s[k][m]-s[i-1][m]-s[k][j-1]+s[i-1][j-1];
if (sum>max1) max1=sum;
} } } I had the same problem. Firstly I used array of short and there was overflow in sum (max possible sum is 127 * 100 * 100 = 1270000 > 32767). Then I changed type to int and got AC :) I was little discouraged when my O(n^4) solution got AC.What remains the purpose of Dp ,if I could do it by complete search. Please mail me the O(n^3),O(n^2),O(n) solution for this task,any or all complexity written here. My mail id is royalbird.raman@gmail.com thanks for your support O(n) cannot be achieved in this problem, because of O(n^2) input. I think you use a kind of DP when you sum the numbers in every rectangle. (In fact, the most complete search has the complexity O(n^6)) =)) Please can anybody tell me what is test case #11 I get WA in Test#3..can anybody give me some test please? all test that i found passed right.. thanks! My program gets WA #5. Did anybody have the same problem? Program works correctly with all inputs I have found. Edited by author 09.09.2012 13:01 Gimme some tests, please :) All tests that I found my program passed right, I can't understand my mistake. Now I have WA4 :) Edited by author 08.07.2012 10:07 can anybody explain me an idea of N^2? I think there is no O(N^2) solution, but who knows? Maybe, I'm not right. Now my AC solution is nearly O(N^3) (something like N^3-N^4 operation) - it's enough. try this: sample input: 2 -1 -2 -3 -4 sample output: -1 |
|