nikunjsoni

363

Apr 6th, 2021
108
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     int maxSumSubmatrix(vector<vector<int>>& m, int k) {
  4.         int res = INT_MIN, rows = m.size(), cols = m[0].size();
  5.         for (int l = 0; l < cols; ++l) {
  6.             vector<int> sums(rows);
  7.             for (int r = l; r < cols; ++r) {
  8.                 int kadane = 0, max_kadane = INT_MIN;
  9.                 for (int i = 0; i < rows; ++i) {
  10.                     sums[i] += m[i][r];
  11.                     kadane = max(kadane + sums[i], sums[i]);
  12.                     max_kadane = max(max_kadane, kadane);
  13.                 }
  14.                 if (max_kadane <= k) {
  15.                     res = max(res, max_kadane);
  16.                     continue;
  17.                 }
  18.                 set<int> s = {0};
  19.                 int run_sum = 0;
  20.                 for (int sum : sums) {
  21.                     run_sum += sum;
  22.                     auto it = s.lower_bound(run_sum - k);
  23.                     if (it != s.end())
  24.                         res = max(res, run_sum - *it);
  25.                     s.insert(run_sum);
  26.                 }
  27.             }
  28.         }
  29.         return res;
  30.     }
  31. };
RAW Paste Data