难度: Medium
给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个 非空 小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, ... , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik] 。
请你返回老师创建的小组能得到的最大实力值为多少。
示例 1：
输入：nums = [3,-1,-5,2,5,-9] 输出：1350 解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。
示例 2：
输入：nums = [-4,-5,-4] 输出：20 解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。
提示：
1 <= nums.length <= 13-9 <= nums[i] <= 9运行时间: 24 ms
内存: 16.0 MB
class Solution:
def maxStrength(self, A: List[int]) -> int:
ans = dpMin = dpMax = A[0]
for x in A[1:]:
ndpMin = min(dpMin, dpMin * x, dpMax * x, x)
ndpMax = max(dpMax, dpMin * x, dpMax * x, x)
dpMin, dpMax = ndpMin, ndpMax
ans = max(ans, dpMax)
return ans
此题解采用动态规划的方法来解决问题。定义两个变量 dpMin 和 dpMax 分别存储当前遍历到的元素之前的最小乘积和最大乘积。初始化这两个变量为数组的第一个元素。随后，对数组中的每一个元素进行遍历，计算与当前元素相乘后可能得到的新的最小乘积和最大乘积。这一步是通过比较当前最大最小乘积与当前元素相乘的结果，以及当前元素本身来确定。每次遍历更新结果的最大值，即可能的最大实力值。这种方法有效处理了负数乘积变正数的情况，从而确保能找到真正的最大乘积。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def maxStrength(self, A: List[int]) -> int:
ans = dpMin = dpMax = A[0] # 初始化答案及最大最小乘积为数组第一个元素
for x in A[1:]: # 遍历数组中的剩余元素
ndpMin = min(dpMin, dpMin * x, dpMax * x, x) # 计算新的最小乘积
ndpMax = max(dpMax, dpMin * x, dpMax * x, x) # 计算新的最大乘积
dpMin, dpMax = ndpMin, ndpMax # 更新当前最小最大乘积
ans = max(ans, dpMax) # 更新可能的最大实力值
return ans # 返回最大实力值
在处理涉及乘积的数组中，负数的存在使得最小乘积和最大乘积的状态都可能影响最终的最大实力值。特别是当乘积涉及负数时，当前的最小乘积（如果是负数）乘以一个负数可能变成一个较大的正数，从而成为可能的最大实力值。因此，同时维护最小乘积和最大乘积可以确保能够捕捉到这种由负数乘积转变的情况，从而找到真正的最大实力值。
在每次更新最大乘积和最小乘积时，包括当前元素x是必要的，因为x本身可能比之前的任何乘积都大或都小。例如，如果之前的最大乘积是正数而x是一个较大的正数，或者之前的最小乘积是正数而x是一个较小的负数，那么x本身可能成为新的最大或最小乘积。这种单独考虑确保了每次都能重新评估并捕捉到可能的最大或最小乘积。
使用临时变量ndpMin和ndpMax进行更新是为了防止在计算过程中覆盖掉原始的dpMin或dpMax值，从而影响后续计算。如果直接更新dpMin和dpMax，当前的dpMin值可能会在计算dpMax之前被修改，这会导致计算错误的结果。使用临时变量可以确保在整个迭代过程中dpMin和dpMax的原始值保持不变，直到所有计算完成后再统一更新，从而保证计算的正确性。
如果数组中包含0，算法会在遍历到0时将其考虑为一个可能的最小或最大乘积。由于0乘以任何数都是0，这意味着遍历到0的时候，当前的最大乘积和最小乘积都可能变为0。在算法中，0被包括在比较（新的最小乘积和最大乘积）中，因此如果0比之前的最大乘积大或者比之前的最小乘积小，它会被设置为新的最大或最小乘积。由于最大实力值是所有遍历过程中最大乘积的最大值，包含0可能会导致某些乘积序列重置为0，从而影响求最大实力值的过程。