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 {3134179b33eee035b545902bde6c1a95dd50f4b6dd1c7a254d8d16b9c4e64f13} 2
            val y = (i - 1) {3134179b33eee035b545902bde6c1a95dd50f4b6dd1c7a254d8d16b9c4e64f13} 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
    }
}