LeetCode日本語修行9日目- [363-総和はKまで最大のマトリクス]
Max Sum of Rectangle No Larger Than K
参考：https://leetcode.com/problems/max-sum-of-rectangle-no-larger-than-k/
問題の内容:
m x n の行列と整数 k があります，総和はKまで最大のマトリクスの最大和を返す．
総和はKまで最大のマトリクスが存在することが保証されています。
例:
例1:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
例2:
Input: matrix = [[2,2,-1]], k = 3
Output: 3
ヒント:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-105 <= k <= 105
今日の問題は、最大サブアレイを理解の上に、回答すると、わりと簡単になると思います。
対応の問題はこちら：https://leetcode.com/problems/maximum-subarray/
最大サブアレイの計算はArrayに対しての計算ですが、今回対象はMatrixです。
まずは、問題を変換します。
Matrixの形は以下：
[8,2,4,4,9]
[1,7,3,4,3]
[2,1,6,4,5]
[7,2,3,9,2]
太字になった部分の総和を計算する
sum
8+2+4 [8,2,4,4,9]
1+7+3 [1,7,3,4,3]
2+1+6 [2,1,6,4,5]
7+2+3 [7,2,3,9,2]
そして、sumMatrix = sumRow1 + sumRow2 + sumRow3 + sumRow4
即ち sumMatrix : [sumRow1,sumRow2,sumRow3,sumRow4]
sumMatrixの最大サブアレイの計算になりました！
class Solution {
fun maxSumSubmatrix(matrix: Array<IntArray>, k: Int): Int {
var rows = matrix.size
var cols = matrix[0].size
var answer = Integer.MIN_VALUE
for(left in 0 until cols){
var rowSum = IntArray(rows)
for(right in left until cols){
for(i in 0 until rows){
rowSum[i] += matrix[i][right]
}
answer = Math.max(answer,dpmax(rowSum,k))
}
}
return answer
}
fun dpmax(array:IntArray,k:Int): Int{
var max = Integer.MIN_VALUE
for(left in 0 until array.size){
var sum = 0
for(right in left until array.size){
sum += array[right]
if(sum > max && sum <= k){
max = sum
}
}
}
return max
}
}
Author And Source
この問題について(LeetCode日本語修行9日目- [363-総和はKまで最大のマトリクス]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/d23ec0dbc6e86ae9f240著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .