108

SUBMITTED BY: Guest

DATE: Dec. 25, 2013, 3:01 p.m.

FORMAT: Text only

SIZE: 2.5 kB

Raw Download

HITS: 1884

Report
  1. #include <algorithm>
  2. #include <cmath>
  3. #include <cstdio>
  4. #include <cstring>
  5. #include <iomanip>
  6. #include <iostream>
  7. #include <limits.h>
  8. #include <map>
  9. #include <queue>
  10. #include <set>
  11. #include <stack>
  12. #include <string>
  13. #include <vector>
  14. using namespace std;
  15. typedef pair<int,int> ii;
  16. typedef vector<int> vi;
  17. typedef vector<ii> vii;
  18. typedef set<int> si;
  19. typedef set<ii> sii;
  20. #define MP make_pair
  21. #define PB push_back
  22. #define REP(i,a) for (int i = 0; i < int(a); i++)
  23. #define FOR(i,a,b) for ( int i = int(a); i <= int(b); ++i )
  24. #define FORD(i,a,b) for ( int i = int(a); i >= int(b); --i )
  25. #define TR(c,it) for( typeof(c.begin()) it = c.begin(); it != c.end(); ++it )
  26. #define TRR(c,it) for( typeof(c.rbegin()) it = c.rbegin(); it != c.rend(); ++it )
  28. const int INF = 1<<29;
  29. typedef long long int lli;
  31. const int MAXROW = 100;
  32. const int MAXCOL = 100;
  34. int matrix[MAXROW][MAXCOL];
  36. int kadane( int * arr, int & start, int & finish, int n )
  37. {
  38. int sum = 0, maxSum = INT_MIN;
  39. finish = -1;
  41. int local_start = 0;
  42. FOR( i, 0, n-1 )
  43. {
  44. sum += arr[i];
  45. if ( sum < 0 )
  46. {
  47. sum = 0;
  48. local_start = i + 1;
  49. }
  50. else if ( sum > maxSum )
  51. {
  52. maxSum = sum;
  53. start = local_start;
  54. finish = i;
  55. }
  56. }
  57. if ( finish != -1 )
  58. return maxSum;
  59. maxSum = arr[0];
  60. start = finish = 0;
  61. FOR( i, 1, n-1 )
  62. {
  63. if ( sum > maxSum )
  64. {
  65. maxSum = sum;
  66. start = finish = i;
  67. }
  68. }
  69. return maxSum;
  70. }
  72. int findMaxSum( int row, int col )
  73. {
  74. int maxSum = INT_MIN, finalLeft, finalRight, finalTop, finalBottom;
  75. int left, right;
  76. int temp[row], sum, start, finish;
  78. FOR( left, 0, col - 1 )
  79. {
  80. memset( temp, 0, sizeof(temp) );
  81. FOR( right, left, col-1 )
  82. {
  83. FOR( i, 0, row-1 )
  84. temp[i] += matrix[i][right];
  85. sum = kadane( temp, start, finish, row );
  86. if ( sum > maxSum )
  87. {
  88. maxSum = sum;
  89. finalLeft = left;
  90. finalRight = right;
  91. finalTop = start;
  92. finalBottom = finish;
  93. }
  94. maxSum = max( sum, maxSum );
  95. }
  96. }
  97. return maxSum;
  98. }
  100. int main( )
  101. {
  102. int n;
  104. while ( scanf("%d", &n) == 1 )
  105. {
  106. FOR( i, 0, n-1 )
  107. FOR( j, 0, n-1 )
  108. scanf("%d", &matrix[i][j]);
  109. printf("%d\n", findMaxSum( n, n ));
  110. }
  113. return 0;
  114. }
comments powered by Disqus