1911. 最大子序列交替和 - Kotlin 逆序DP

原题地址：https://leetcode.cn/problems/maximum-alternating-subsequence-sum/description/

题解

设dp[i][0]是子数组[i:]的最大子序列交替和，dp[i][1]是子数组[i:]的最小子序列交替和

我们从后往前考虑：

当子数组[i:]的子序列以nums[i]起始时，我们实际上是在子数组[i+1:]中找到一个子序列，然后在子序列的最前方插入了一个nums[i]

• 此时该子序列的交替和为：nums[i]-子序列的交替和
  • 因为插入该nums[i]后，后面的每一个奇数都变成了偶数，每一个偶数都变成了奇数，因此子序列的这部分交替和变成了原来的相反数
• 对于子数组[i:]中以nums[i]起始的最大子序列交替和，实际上是子数组[i+1:]中的最小子序列交替和的相反数加上nums[i]
• 对于子数组[i:]中以nums[i]起始的最小子序列交替和，实际上是子数组[i+1:]中的最大子序列交替和的相反数加上nums[i]

当子数组[i:]的子序列不以nums[i]起始时：

• 子数组[i:]中不以nums[i]起始的最大子序列交替和，等于子数组[i+1:]中的最大子序列交替和
• 子数组[i:]中不以nums[i]起始的最小子序列交替和，等于子数组[i+1:]中的最小子序列交替和
• 这里通过一个max和min变量进行维护即可

两种情况分别取其较大/较小值即可，即：

子数组[i:]的最大子序列交替和：

子数组[i:]的最大小序列交替和：

空间复杂度：O(N)

时间复杂度：O(N)

class Solution {
    fun maxAlternatingSum(nums: IntArray): Long {
        val dp = Array(nums.size) { Array<Long>(2) { 0 } }
        var max: Long = Long.MIN_VALUE
        var min: Long = Long.MAX_VALUE
        for (i in nums.size - 1 downTo 0) {
            if (i == nums.size - 1) {
                dp[i][0] = nums[i].toLong()
                dp[i][1] = 0
            } else {
                dp[i][0] = Math.max(-min + nums[i], max)
                dp[i][1] = Math.min(-max + nums[i], min)
            }
            max = Math.max(max, dp[i][0])
            min = Math.min(min, dp[i][1])
        }
        return max
    }
}