LeetCode 363. 矩形区域不超过 K 的最大数值和（DP+set二分查找）

示例:
输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2 
解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，
且 2 是不超过 k 的最大数字（k = 2）。

说明：
矩阵内的矩形区域面积必须大于 0。
如果行数远大于列数，你将如何解答呢？

class Solution {
public:
    int maxSumSubmatrix(vector<vector<int>>& mat, int k) {
    	if(mat.empty() || mat[0].empty())
    		return 0;
    	int m = mat.size(), n = mat[0].size(), i, j1, j2;
    	int sum, tempmax, maxsum = INT_MIN, prefix;
    	vector<int> sumCols(m);
    	for(j1 = 0; j1 < n; ++j1)
    	{
    		sumCols.clear();
    		sumCols.resize(m);
    		for(j2 = j1; j2 < n; ++j2)
    		{	//列的左右边界组合
    			for(i = 0; i < m; ++i)
    				sumCols[i] += mat[i][j2];//行向求和
    			sum = tempmax = INT_MIN;   		
	    		for(i = 0; i < m; ++i)
	    		{	//对上面的和，求最大连续子序列和，DP
	    			if(sum > 0)
	    				sum += sumCols[i];
	    			else
	    				sum = sumCols[i];
	    			tempmax = max(sum, tempmax);//临时的最大子序列和
                    if(sum <= k)//更新答案
	    			    maxsum = max(maxsum, sum);
	    		}
	    		if(tempmax == k || maxsum==k)
	    			return k;//找到上限直接返回
	    		if(tempmax < k)//最大连续子序列和小于 k，进行下一轮
	    			continue;
	    		//最大连续子序列和 大于 k，还要继续查找 有可能 <= k 的
	    		set<int> s;
                s.insert(0);//第一个就是k的时候，可以找到
                prefix = 0;//利用前缀和，在set中二分查找
    			for(i = 0; i < m; ++i)
    			{
                    prefix += sumCols[i];
                    auto it = s.lower_bound(prefix-k);
                    s.insert(prefix);
                    if(it != s.end())
                    {
                    	int SUM = prefix-(*it);
                    	if(SUM > maxsum)
                    		maxsum = SUM;
                    }
                    if(maxsum == k)
                    	return k;
                }
    		}
    	}
    	return maxsum;
    }
};