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