Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1768
A grid that wraps both horizontally and vertically is called a torus. Given a torus where each cell contains an integer, determine the sub-rectangle with the largest sum. The sum of a sub-rectangle is the sum of all the elements in that rectangle. The grid below shows a torus where the maximum sub-rectangle has been shaded. Input The first line in the input contains the number of test cases (at most 18). Each case starts with an integer N (1 ≤ N ≤ 75) specifying the size of the torus (always square). Then follows N lines describing the torus, each line containing N integers between -100 and 100, inclusive. Output For each test case, output a line containing a single integer: the maximum sum of a sub-rectangle within the torus.
Sample Input 2 5 1 -1 0 0 -4 2 3 -2 -3 2 4 1 -1 5 0 3 -2 1 -3 2 -3 2 4 1 -4 3 1 2 3 4 5 6 7 8 9
Sample Output 15 45
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// idea: twice the initial length of matrix to handle wrap-around
int main()
{
int t,n;
cin >> t;
while(t--){
cin >> n;
vector < vector<int>> dp(n*2+1,vector<int>(n*2+1));
for(int i=1;i < =n;i++){
for(int j=1;j < =n;j++){
scanf("%d",&dp[i][j]);
dp[i][j+n] = dp[i+n][j] = dp[i+n][j+n] = dp[i][j];
}
}
// running sum
for(int i=1;i < =2*n;i++)
for(int j=1;j < =2*n;j++){
dp[i][j] += (dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]);
}
// dp
int res = INT_MIN;
for(int i=1;i < =n;i++) for(int j=1;j < =n;j++)
for(int k=i;k < i+n;k++) for(int l=j;l < j+n;l++){
int cur = dp[k][l] - dp[i-1][l] - dp[k][j-1] + dp[i-1][j-1];
res = max(cur,res);
}
printf("%d\n",res);
}
}
Input
5
1 -1 0 0 -4
2 3 -2 -3 2
4 1 -1 5 0
3 -2 1 -3 2
-3 2 4 1 -4
3
1 2 3
4 5 6
7 8 9
Output
45
Demonstration
UVA Online Judge solution - 10827-Maximum sum on a torus - UVA Online Judge solution in C,C++,java