363. Max Sum of Rectangle No Larger Than K

LeviDing 發布于2019-08-16 10:29 / 2029人閱讀

摘要：題目鏈接參考里的解釋先是如何在矩陣里找的問題，參考視頻然后就是一個里面找不大于的最大值問題了要找到最大的用就是，就是來做了。行和列哪個打就用另一個掃。另外找最大不超過的還可以用，參考

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/...

云服務器 GPU云服務器 Larger than CDN363 Rectangle

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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