AOJ- 0098 Maximum Sum Sequence II Scala

Maximum Sum Sequence II Scala
部分行列の和の最大値 | Aizu Online Judge

何回も見たことのあるような問題。。。。。
まぁとりあえず、この問題の最初の考えは、
左上から右下までの総和を出す（各場所の）。

Sample Input

 3
 1 -2 3
 -4 5 6
 7 8 -9

で考える

1 -2 3　→　1 0 0　→　1 -1 0  →　1 -1 2  →　1 -1 2  →　1 -1 2  →　1 -1 2
-4 5 6　→　0 0 0  →　0 0 0   →　0 0 0   →　-3 0 0  →　-3 0 0  →　-3 0 9
7 8 -9　→　0 0 0  →　0 0 0   →　0 0 0   →  0 0 0   →　0 0 0   →　0 0 0
                                                                  ↓↓↓
↓↓↓←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←←
1 -1 2 →　1 -1 2  →　1 -1 2
-3 0 9 →　-3 0 9　→　-3 0 9
4 0 0　→　4 15 0　→　4 15 15　　　  　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

計算　...　map 　　[ i - 1 ] [ j ]　　+　　[ i ] [ j - 1 ]　　 -　　[ i - 1 ] [ j - 1 ]

次に
総和からその場から区切りの場所まで削る。
削る際に重なってる部分多く削るので、その部分を足す

計算... [最初での総和]　 -　 [区切りまでの削り]　 -　 [区切りまでの削り] 　+　 [削りの重なり]

ではソースコード！！！！

import scala.io.StdIn._
import scala.math._
object Main{
    def main(args: Array[String]): Unit = {
        lazy val n = readInt
        var map = Array.ofDim[Int](n + 1, n + 1)
        for(i <- 1 to n){
              var temp = readLine.split(" ").map(_.toInt)
            for(j <- 1 to n)map(i)(j) = map(i)(j - 1) + map(i - 1)(j) -  map(i - 1)(j - 1) + temp(j - 1)
        }
        var max = map(1)(1)
        for(i <- 1 to n ;j <- 1 to n;k <- i to n;l <- j to n) max = math.max(max,map(k)(l) + map(i - 1)(j - 1) - map(i - 1)(l) - map(k)(j - 1))   
        
        
        println(max)
  }
}