918. 环形子数组的最大和 - Kotlin 最大子数组和+最小子数组和 DP

Problem: 918. 环形子数组的最大和

思路

官方题解的这张图片很好的解释了这道题：

• 一是要求这个数组的连续子数组最大和
• 二是要求这个数组的一段以0起始的子数组和一段以n结尾的子数组的最大和

第一点我们可以很简单地53. 最大子数组和的做法做出来：

• dp[i]记录以i结尾的子数组的最大和，每次判断dp[i-1]
• 如果dp[i-1]>0则说明我们可以将i-1结尾的子数组的末尾接上一个i使之变为i结尾的子数组
• 如果dp[i-1]<=0则说明我们进行上述操作是有害无益的，相比之下抛弃i-1结尾的子数组，令i重新开始一个以自身为元素的长度为1的子数组是更好的选择

考虑第二点如何实现：

由于两端数组必然包含首尾，这两段子数组的和实际上等于整个数组的元素和减去中间那段子数组的元素和，那么反之，我们求连续子数组的最小和，用整个数组的元素和sum减去这个最小和，就是这种情况下的最大和

所以这道题本质上是同时求最大子数组和和最小子数组和

边界情况：对于情况二，考虑到我们是用整个数组减去中间的子数组的，应当舍弃掉子数组为全部元素的情况，这样减去后实际上是空数组，不符合题意要求

复杂度

• 时间复杂度:
• 空间复杂度:

Code

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        val dp=Array(nums.size){ IntArray(2){0} }
        val sum=nums.sum()
        var max=Int.MIN_VALUE
        for(i in nums.indices){
            dp[i][0]=(if(i>0&&dp[i-1][0]>0) dp[i-1][0] else 0)+nums[i]
            dp[i][1]=(if(i>0&&dp[i-1][1]<0) dp[i-1][1] else 0)+nums[i]

            max=Math.max(max,dp[i][0])
            if(sum!=dp[i][1])
            max=Math.max(max,sum-dp[i][1])
        }
        return max
    }
}