Leetcode 363 Solution

This article provides solution to leetcode question 363 (max-sum-of-rectangle-no-larger-than-k)
Categories:
Tags:
Access this page by simply typing in "lcs 363" in your browser address bar if you have bunnylol configured.

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);
        }
    }
};