贪心

题目分析 本题需要首先在数组$nums$中选择一个子数组，并对其中所有元素都乘以或除以$k$，之后在整个数组中选出一个最大的子数组总和。 基本思路 贪心(无法通过) 如果要完全按照题目的顺序进行模拟计算，太过复杂，并且选择所有可能的子数组分别计算的时间复杂度太高，因此正难则反，既然要操作以后求最大的子数组总和，那为什么不能先求出原先$nums$中的最大子数组总和，然后再通过乘除$k$得到最后的答案呢？ 理论上这是可以的，如果已知原先$nums$中的最大子数组总和为$maxSum$，那么答案就有两种情况： 当$maxSum>0$时，为了让最终的答案尽可能的大，就需要将其乘以$k$，即答案为$maxSum\times k$； 当$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$的位置上，一直到竞赛结束后才发现那个测试用例长这样： $$ \begin{align} &nums = \underbrace{[-8,5,-8,10,-8,5,-8,10,\dots,-8,5,-8,10]}_{总共100个-8,5,-8,10循环}\\ &k = 5 \end{align} $$按照上面的贪心算法，首先在$nums$中求出最大子数组和，可以得到$maxSum=10$，之后根据判断条件，即可得到最终的答案是$maxSum\times k=50$，但这并不是正确答案，原因在于如果在原数组中先找最大子数组和，寻找过程中会发现单独一个循环节的和是： $$ -8+5-8+10=-1 $$ 但如果将所有数字都按照题目要求的方式整除$k=5$后，上面的四个数字就会变成： $$ \begin{align} -8&\rightarrow -1\\ 5&\rightarrow 1\\ 10&\rightarrow 2\\ \end{align} $$ 于是四个数字相加就变成了： ...