乘积最大之连续与非联系子数组

文章目录 152.乘积最大子数组2708.一个小组的最大实力值

乘积的最大情况分为两种，一种是 要求子数组是连续的，一种是要求数组是不用连续的 连续可以使用动态规划求解，非连续则使用贪心

152.乘积最大子数组

152.乘积最大子数组

思路分析：由于要求是连续的，那么当前的nums[i]来说，对应的以它结尾的子数组的情况，要么是自己独自开始，要么是接着前一个dp[i-1]的情况，所以总的来说，转移情况可以用动态规划来解决，也就是使用fmax和fmin来记录最大和最小的值

class Solution: def maxProduct(self, nums: List[int]) -> int: # 一样的思路 n = len(nums) fmax = [1]*(n+1) fmin = [1]*(n+1) for i in range(n): fmax[i+1] = max(fmax[i]*nums[i],fmin[i]*nums[i],nums[i]) fmin[i+1] = min(fmax[i]*nums[i],fmin[i]*nums[i],nums[i]) # 直接排除第一个的初始值 return max(fmax[1:]) 2708.一个小组的最大实力值

2708.一个小组的最大实力值

思路分析：该题并不能用动态规划来求解，而是使用贪心来解决

class Solution: def maxStrength(self, nums: List[int]) -> int: zheng = [i for i in nums if i > 0] fu = [i for i in nums if i < 0] # 先记录当前的单个的最大值，当没有正数的时候或者负数的个数为1的时候，结果就是这个max(nums) ans = max(nums) # 不连续的话，用不了动态规划 tmp = 1 # 将全部的正数乘起来 for i in zheng: tmp *= i # 负数的先升序排序，找到偶数对乘起来 fu.sort() if len(fu) >= 2: for i in fu: tmp*= i if len(fu) % 2 == 1: tmp //= fu[-1] # 还得考虑只有一个负数，以及没有正数的情况，更新 if len(zheng) > 0 or len(fu) >= 2: ans = max(ans,tmp) return ans