Leetcode 363 Solution

https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k

Solution

``````class Solution {
public:
int findopt(int a[], int n, int k)
{
set<int> s;
s.insert(0);

int64_t sum = 0;
int64_t opt = INT_MIN;
for (int i = 0; i < n; i++)
{
sum += a[i];

auto it = s.lower_bound(sum - k);
if (it != s.end())
opt = max(opt, sum - *it);

s.insert(sum);
}

return opt;
}

int maxSumSub(vector<vector<int>>& s, int k) {
int m = s.size();
int n = s[0].size();

int opt = INT_MIN;
for (int start = 0; start < m; start++)
{
for (int end = start; end < m; end++)
{
int a[n];

for (int j = 0; j < n; j++)
{
if (start == 0)
a[j] = s[end][j];
else
a[j] = s[end][j] - s[start - 1][j];
}

int tmp = findopt(a, n, k);
opt = max(opt, tmp);
}
}

return opt;
}

int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int m = matrix.size();
if (m == 0)
return 0;
int n = matrix[0].size();
if (n == 0)
return 0;

if (m <= n)
{
vector<vector<int>> s(m, vector<int>(n));

for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i == 0)
s[i][j] = matrix[i][j];
else
s[i][j] = s[i - 1][j] + matrix[i][j];
}
}

return maxSumSub(s, k);
}
else
{
vector<vector<int>> s(n, vector<int>(m));

for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (i == 0)
s[i][j] = matrix[j][i];
else
s[i][j] = s[i - 1][j] + matrix[j][i];
}
}

return maxSumSub(s, k);
}
}
};
``````