Leetcode 53. 最大子序和

53. 最大子序和

同类型题：47 | 面试题：乘积最大子序列

class Some53Solution {
    fun maxSubArray(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        val dp = Array(2) {
            IntArray(2) { nums[0] }
        }
        var res = nums[0]
        for (i in 1 until nums.size) {
            //动态下标
            val x = i % 2
            val y = (i - 1) % 2
            //获取正数 max
            dp[x][0] = Math.max(Math.max(dp[y][0] + nums[i], dp[y][1] + nums[i]), nums[i])
            //获取负数 -max
            dp[x][1] = Math.min(Math.min(dp[y][0] + nums[i], dp[y][1] + nums[i]), nums[i])
            res = Math.max(res, dp[x][0])
        }
        return res
    }
}