363.md

区间不小于k的最大和可以nlogn 求出来

无脑的n^4解法

int max(int a, int b){
    return a>b?a:b;
}
int help(int *a, int matrixColSize, int k){
    int minn, ans = 1<<31;
    for(int j = 0; j<matrixColSize; ++j){
        minn = 0;
        for(int i = j; i< matrixColSize; ++i){
            if(minn == 0)
                minn = a[i];
            else
                minn += a[i];
            if(minn <= k)
                ans = max(ans, minn);
        }
    }
    return ans;
}

int maxSumSubmatrix(int** matrix, int matrixRowSize, int matrixColSize, int k) {
    int minn = 1<<31;
    for(int i = 0; i< matrixRowSize; ++i){
        minn = max(minn, help(matrix[i], matrixColSize, k));
        for(int j = i+1; j < matrixRowSize; ++j){
            for(int k = 0; k < matrixColSize; ++k)
                matrix[i][k] += matrix[j][k];
            minn = max(minn, help(matrix[i], matrixColSize, k));
        }
    }
    return minn;
}