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
    }
}