aboutsummaryrefslogtreecommitdiff
path: root/max_sum_rectangle.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'max_sum_rectangle.cpp')
-rw-r--r--max_sum_rectangle.cpp33
1 files changed, 0 insertions, 33 deletions
diff --git a/max_sum_rectangle.cpp b/max_sum_rectangle.cpp
deleted file mode 100644
index 9b252e1..0000000
--- a/max_sum_rectangle.cpp
+++ /dev/null
@@ -1,33 +0,0 @@
-#include "leetcode.h"
-
-class Solution {
-public:
- int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
- int ans = INT_MIN, rows = matrix.size(), cols = matrix[0].size();
- for (int l = 0; l < cols; ++l) {
- vector<int> sums(rows);
- for (int r = l; r < cols; ++r) {
- int pMin = 0, pMax = INT_MIN;
- for (int i = 0; i < rows; ++i) {
- sums[i] += matrix[i][r];
- pMin = max(pMin + sums[i], sums[i]);
- pMax = max(pMax, pMin);
- }
- if (pMax <= k) {
- ans = max(ans, pMax);
- continue;
- }
- set<int> s = {0};
- int runSum = 0;
- for (int sum : sums) {
- runSum += sum;
- auto it = s.lower_bound(runSum - k);
- if (it != end(s))
- ans = max(ans, runSum - *it);
- s.insert(runSum);
- }
- }
- }
- return ans;
- }
-};