410.swift

private class SolutionDP1 {
    // DP
    public func splitArray(_ nums: [Int],_ m: Int) -> Int {
        let n = nums.count
        
        /**
         ```
         dp [n+1:2]
         [
         min, max, max, ....
         min, max, max, ....
         ]
         sum [n+1:2]
         [
         0, Σ0, Σ1, Σ2, ... , Σn]
         ```
         */
        var dp: [[Int]] =  Array(repeating: Array(repeating: .max, count: n+1), count: 2)
        let sum: [Int] = {
            var sum = Array(repeating: 0, count: n + 1)
            for i in 0..<n {
                sum[i + 1] = nums[i] + sum[i]
            }
            print(sum)
            return sum
        }()
        dp[0][0] = -1
        dp[1][0] = -1
        
        
        /// 1...group
        for i in 1...m {
            /// 1...length
            for j in 1...n {
                var k = i - 1
            whileLoop:while true {
                guard k < j else {break whileLoop}
                let d = sum[j] - sum[k]
                let t = dp[(i-1)&1][k]
                dp[i&1][j] = min(dp[i&1][j],
                                 max(t, d))
                k += 1
            }
            }
        }
        return dp[m&1][n]
    }
}