3976.乘以系数后最大子数组和

题目分析

本题需要首先在数组$nums$中选择一个子数组，并对其中所有元素都乘以或除以$k$，之后在整个数组中选出一个最大的子数组总和。

基本思路

贪心(无法通过)

如果要完全按照题目的顺序进行模拟计算，太过复杂，并且选择所有可能的子数组分别计算的时间复杂度太高，因此正难则反，既然要操作以后求最大的子数组总和，那为什么不能先求出原先$nums$中的最大子数组总和，然后再通过乘除$k$得到最后的答案呢？

理论上这是可以的，如果已知原先$nums$中的最大子数组总和为$maxSum$，那么答案就有两种情况：

1. 当$maxSum>0$时，为了让最终的答案尽可能的大，就需要将其乘以$k$，即答案为$maxSum\times k$；
2. 当$maxSum<0$时，为了让答案尽可能大，则需要将其除以$k$，即答案为$\lceil \frac{maxSum}{k} \rceil$；

因此根据上面的分析可以简单写出以下贪心代码：

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        sum_num = nums[0]
        max_sum_num = nums[0]
        for i in nums[1:]:
            if sum_num < 0:
                sum_num = 0
            sum_num += i
            max_sum_num = max(sum_num,max_sum_num)

        if max_sum_num > 0:
            max_sum_num *= k
        else:
            max_sum_num = -(abs(max_sum_num)//k)
        return max_sum_num

可惜的是，在提交之后，上面代码并不能通过全部测试用例，而是卡在了$717/718$的位置上，一直到竞赛结束后才发现那个测试用例长这样：

按照上面的贪心算法，首先在$nums$中求出最大子数组和，可以得到$maxSum=10$，之后根据判断条件，即可得到最终的答案是$maxSum\times k=50$，但这并不是正确答案，原因在于如果在原数组中先找最大子数组和，寻找过程中会发现单独一个循环节的和是：

但如果将所有数字都按照题目要求的方式整除$k=5$后，上面的四个数字就会变成：

于是四个数字相加就变成了：

可以发现原先计算过程中和是负数的几个数字竟然在除法操作后和变成了正数，这就是贪心算法会出错的原因，在面对整除操作时，原先几个数之和除以一个数字得到的结果和原先几个数分别除以一个数字再相加得到的结果完全不同，没办法，只能探索其他解法了。

动态规划

注意到，如果选取了$nums$中的一个子数组进行了乘$k$或除$k$的操作，那么对于其中每一个位置$i$，它的状态就有以下三种情况：

1. 在位置$i$之前还没有开始进行操作；
2. 在位置$i$还在操作（乘或除$k$）；
3. 在位置$i$之前操作已经结束。

针对这三种情况即可定义四个动态规划数组如下：

1. $dp0[i]$表示在$[0,i]$之间未开始操作时，以位置$i$结尾的最大子数组总和；
2. $dp1_m[i]$表示$[0,i]$之间已经开始乘$k$操作，且还未结束时，以位置$i$结尾的最大子数组总和；
3. $dp1_d[i]$表示$[0,i]$之间已经开始除$k$操作，且还未结束时，以位置$i$结尾的最大子数组总和；
4. $dp2[i]$表示所有操作已经在$i$之前结束时，以位置$i$结尾的最大子数组总和。

接下来考虑递推方程式。

对于$dp0[i]$，根据定义，它可能通过以下两种途径得到：

1. 从$i$开始重新累加子数组总和，不考虑之前的值，即$nums[i]$；
2. 从$i-1$转移，由于$i-1$同样没有开始操作，则答案为$dp0[i-1]+nums[i]$；

对于$dp1_m[i]$，根据定义，它可能通过以下三种途径得到：

1. 从$i$开始重新累加子数组总和，不考虑之前的值，即$nums[i]\times k$；
2. 从$i-1$转移，且$i-1$还未开始操作，即$dp0[i-1]+nums[i]\times k$；
3. 从$i-1$转移，且$i-1$已经开始操作，即$dp1_m[i-1]+nums[i]\times k$；

对于$dp1_d[i]$，也是和$dp1_m[i]$同样的三种转移方式，就不重复说明。

最后对于$dp2[i]$，根据定义，它可能通过以下两种途径得到：

1. 从$i-1$转移，且$i-1$之前已经完成所有操作，即$dp2[i-1]+nums[i]$；
2. 从$i-1$转移，且$i-1$是最后一个进行操作的位置，即$dp1[i-1]+nums[i]$； (注意两个$dp1$都需要考虑进去)

根据上面方式计算出所有值，答案就是四个数组中最大值的最大值。 （这里可以采用滚动计算，从而降低空间复杂度）

复杂度

时间复杂度：$O(n)$ 空间复杂度：$O(1)$

代码

class Solution:
    def maxSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp0 = nums[0]
        dp1_m = nums[0]*k
        dp1_d = int(nums[0]/k)
        dp2 = -10**18 # 由于第一个位置不可能结束所有操作，因此对应值为-inf

        res = max(dp0, dp1_m, dp1_d, dp2)
        for i in nums[1:]:
            ndp0 = max(i, dp0+i)
            ndp1_m = max(i*k, dp0+i*k, dp1_m+i*k)
            ndp1_d = max(int(i/k), dp0+int(i/k), dp1_d+int(i/k))
            ndp2 = max(dp2+i, dp1_m+i, dp1_d+i)

            dp0 = ndp0
            dp1_m = ndp1_m
            dp1_d = ndp1_d
            dp2 = ndp2
            res = max(res, dp0, dp1_m, dp1_d, dp2)
        return res