1749. 任意子数组和的绝对值的最大值 - Kotlin 动态规划 最大(小)子数组和

Problem: 1749. 任意子数组和的绝对值的最大值

思路

考虑以结尾的子数组和的最大绝对值，有两种情况

• 以结尾的子数组的最大和
• 以结尾的子数组的最小和的绝对值

设为以结尾的子数组的最大和，为以结尾的子数组的最小和

以求子数组最大和为例，对于而言，若，则可以拼接在以的最大子数组后面，反之则不如以自己为起始重新开一个新的长度为1的子数组，即

对于边界条件，由于以结尾的子数组只有他自己，因此

复杂度

• 时间复杂度:

• 空间复杂度:

Code

class Solution {
    fun maxAbsoluteSum(nums: IntArray): Int {
        val dp = Array(nums.size) { index -> IntArray(2) { nums[index] } }
        for (index in 1 until nums.size) {
            dp[index][0] = Math.max(dp[index - 1][0] + nums[index], nums[index])
            dp[index][1] = Math.min(dp[index - 1][1] + nums[index], nums[index])
        }
        return dp.fold(0) { max: Int, value: IntArray -> listOf(max, Math.abs(value[0]), Math.abs(value[1])).max()!! }
    }
}