fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int mat[101][101], pre[101][101];
  4. int n, m;
  5.  
  6. // pre[i][j] -- sum from (1, 1) to (i, j)
  7. void get_sum(){
  8. for(int i=1; i<=n; i++){
  9. for(int j=1; j<=m; j++)
  10. pre[i][j] = pre[i][j-1] + mat[i][j];
  11. }
  12. }
  13.  
  14. int query(int i, int l, int r){
  15. return pre[i][r] - pre[i][l-1];
  16. }
  17.  
  18.  
  19. int main(){
  20. cin >> n; m = n;
  21. for(int i=1; i<=n; i++){
  22. for(int j=1; j<=m; j++){
  23. cin >> mat[i][j];
  24. }
  25. }
  26. get_sum();
  27. int mx = 1e-9;
  28.  
  29. for(int l=1; l<=m; l++){
  30. for(int r=l; r<=m; r++){
  31. int curs = 0;
  32. for(int i=1; i<=n; i++){
  33. curs += query(i, l, r); // curs += arr[i]
  34. mx = max(mx, curs);
  35. if(curs < 0)
  36. curs = 0;
  37.  
  38. }
  39. }
  40. }
  41. cout << mx << endl;
  42. }
  43.  
Success #stdin #stdout 0s 15312KB
stdin
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
stdout
15