Beats 99% CPP soultion with explanation


  • 1
    F

    The idea is brute force check all row ranges[r1, r2], add elements to one dimension array. Use a O(n) algorithm to check if a one dimension array has a max sum range larger than K, if yes, then brute force search the array to find the max sum range lower than K, otherwise mark it and check next row combination.

    class Solution {
        int maxSumArray(vector<int> & arr, int k) {
            int sum = 0, maxS = INT_MIN;
            for (int i = 0; i < arr.size(); i++) {
                sum += arr[i];
                maxS = max(sum, maxS);
                if (maxS == k ) return maxS;
                if (sum < 0) sum = 0;
            }
            if (maxS <= k) return maxS;
            maxS = INT_MIN;
            for (int i = 0; i < arr.size(); i++) {
                sum = 0;
                for (int j = i; j < arr.size(); j++) {
                    sum += arr[j];
                    if (sum == k) return sum;
                    if (sum < k && sum > maxS) maxS = sum;
                }
            }
            return maxS;
        }
    public:
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
            if (matrix.empty()) return 0;
            int maxS = INT_MIN;
            for (int r1 = 0; r1 < matrix.size(); r1 ++) {
                vector<int> arr(matrix[r1].size(), 0);
                for (int r2 = r1; r2 < matrix.size(); r2 ++) {
                    for (int c = 0; c < matrix[r1].size(); c++) {
                        arr[c] += matrix[r2][c];
                    }
                    int ms = maxSumArray(arr, k);
                    if (ms == k) return ms;
                    if (ms < k && ms > maxS) maxS = ms;
            }
            }
            return maxS;
        }
    };
    

  • 0
    F

    improved to O(n*log(n))

    https://www.quora.com/Given-an-array-of-integers-A-and-an-integer-k-find-a-subarray-that-contains-the-largest-sum-subject-to-a-constraint-that-the-sum-is-less-than-k

    class Solution {
        int maxSumArray(vector<int> & arr, int k) {
            int sum = 0, maxS = INT_MIN;
            for (int i = 0; i < arr.size(); i++) {
                sum += arr[i];
                maxS = max(sum, maxS);
                if (maxS == k ) return maxS;
                if (sum < 0) sum = 0;
            }
            if (maxS <= k) return maxS;
            maxS= INT_MIN;
            set<int>sums;
            sum = 0;
            sums.insert(0);
            for (int i = 0; i < arr.size(); i++) {
                sum += arr[i];
                auto it = sums.lower_bound(sum - k);
                if (it != sums.end()) maxS = max(sum - *it, maxS);
                sums.insert(sum);
            }
            return maxS;
        }
    public:
        int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
            if (matrix.empty()) return 0;
            int maxS = INT_MIN;
            for (int r1 = 0; r1 < matrix.size(); r1 ++) {
                vector<int> arr(matrix[r1].size(), 0);
                for (int r2 = r1; r2 < matrix.size(); r2 ++) {
                    for (int c = 0; c < matrix[r1].size(); c++) {
                        arr[c] += matrix[r2][c];
                    }
                    int ms = maxSumArray(arr, k);
                    if (ms == k) return ms;
                    if (ms < k && ms > maxS) maxS = ms;
            }
            }
            return maxS;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.