資訊專欄INFORMATION COLUMN
摘要：題目鏈接參考里的解釋先是如何在矩陣?yán)镎业膯?wèn)題，參考視頻然后就是一個(gè)里面找不大于的最大值問(wèn)題了要找到最大的用就是，就是來(lái)做了。行和列哪個(gè)打就用另一個(gè)掃。另外找最大不超過(guò)的還可以用，參考
363. Max Sum of Rectangle No Larger Than K
題目鏈接：https://leetcode.com/problems...
參考discussion里的解釋：
https://discuss.leetcode.com/...
先是如何在2d矩陣?yán)镎襪ax sum的問(wèn)題，參考視頻：
https://www.youtube.com/watch...
然后就是一個(gè)array里面找不大于k的最大值問(wèn)題了:
https://www.quora.com/Given-a...
要找到最大的sum <= k, 用cumulative sum就是cum[j] - k <= cum[i]，upper_bound就是TreeSet來(lái)做了。
行和列哪個(gè)打就用另一個(gè)掃。
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;
}
}
另外找最大不超過(guò)k的range sum還可以用merge sort，參考discussion：
https://discuss.leetcode.com/...
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/69874.html
摘要：思路一暴力循環(huán)如果我們將矩陣中的每個(gè)子矩陣都枚舉出來(lái)，并計(jì)算其元素和，從而得出小于的最大值即可。 題目要求 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...
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 ...
摘要：復(fù)雜度思路參考的思路，對(duì)于，表示在從到的范圍內(nèi)，先手玩家能拿到的最大的硬幣價(jià)值。對(duì)于狀態(tài)，先手玩家有兩種選擇，要么拿的硬幣，要么拿的硬幣左邊一個(gè)的或者右邊一側(cè)的，如果拿左側(cè)的硬幣，如果拿右側(cè)的硬幣，取兩個(gè)值的最大值。 LintCode Coins in a line III There are n coins in a line. Two players take turns to ...
閱讀 4639·2021-11-19 09:59
閱讀 3509·2021-10-12 10:12
閱讀 2723·2021-09-22 15:25
閱讀 3406·2019-08-30 15:55
閱讀 1269·2019-08-29 11:27
閱讀 1548·2019-08-28 18:06
閱讀 2822·2019-08-26 13:41
閱讀 2635·2019-08-26 13:41
