363. Max Sum of Rectangle No Larger Than K

LeviDing 发布于2019-08-16 10:29 / 1936人阅读

摘要：题目链接参考里的解释先是如何在矩阵里找的问题，参考视频然后就是一个里面找不大于的最大值问题了要找到最大的用就是，就是来做了。行和列哪个打就用另一个扫。另外找最大不超过的还可以用，参考

363. Max Sum of Rectangle No Larger Than K

题目链接：https://leetcode.com/problems...

参考discussion里的解释：
https://discuss.leetcode.com/...

先是如何在2d矩阵里找max sum的问题，参考视频：
https://www.youtube.com/watch...

然后就是一个array里面找不大于k的最大值问题了:
https://www.quora.com/Given-a...

要找到最大的sum <= k, 用cumulative sum就是cum[j] - k <= cum[i]，upper_bound就是TreeSet来做了。
行和列哪个打就用另一个扫。

public class Solution {
    public int maxSumSubmatrix(int[][] matrix, int k) {
        if(matrix.length == 0 || matrix.length == 0) return 0;
        
        int m = matrix.length, n = matrix[0].length;
        int global = Integer.MIN_VALUE;
        // m >> n
        for(int j = 0; j < n; j++) {
            int[] col = new int[m];
            for(int p = j; p < n; p++) {
                // cumulative sum
                for(int i = 0; i < m; i++) col[i] += matrix[i][p];
                // maximum array sum < k
                TreeSet set = new TreeSet();
                // include 1 line
                set.add(0);
                int prefixSum = 0, local = Integer.MIN_VALUE;
                for(int sum : col) {
                    prefixSum += sum;
                    // upper_bound
                    Integer cum = set.ceiling(prefixSum - k);
                    if(cum != null) local = Math.max(local, prefixSum - cum);
                    set.add(prefixSum);
                }
                global = Math.max(global, local);
            }
        }
        
        return global;
    }
}

另外找最大不超过k的range sum还可以用merge sort，参考discussion：
https://discuss.leetcode.com/...

服务器托管海外云主机 Larger than CDN363 Rectangle

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69874.html

leetcode363. Max Sum of Rectangle No Larger Than K

摘要：思路一暴力循环如果我们将矩阵中的每个子矩阵都枚举出来，并计算其元素和，从而得出小于的最大值即可。题目要求 Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. E...

nemo 2019-08-16 17:57 评论0 收藏0
[LeetCode] Maximum Size Subarray Sum Equals k

Problem Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isnt one, return 0 instead. Note The sum of the entire nums array is guaranteed to fit ...

MudOnTire 2019-08-15 15:47 评论0 收藏0
LintCode Coins in a line III

摘要：复杂度思路参考的思路，对于，表示在从到的范围内，先手玩家能拿到的最大的硬币价值。对于状态，先手玩家有两种选择，要么拿的硬币，要么拿的硬币左边一个的或者右边一侧的，如果拿左侧的硬币，如果拿右侧的硬币，取两个值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...

focusj 2019-08-14 15:03 评论0 收藏0