Leetcode 363 Solution
This article provides solution to leetcode question 363 (max-sum-of-rectangle-no-larger-than-k)
Access this page by simply typing in "lcs 363" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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);
}
}
};