动态规划 —— 子数组系列-乘积最大子数组

时间:2024-11-15 16:38:43

2. 状态转移方程

  

f[i]分为两种情况:1. 长度为1        nums[i]

  

                              2. 长度大于1分为两种情况:a. nums[i] > 0          nums[i] * f[i-1] 

    

                                                                            b. nums[i] < 0          nums[i] * g[i-1] 

   

f[i] = max(nums[i] ,  nums[i] * f[i-1]  , nums[i] * g[i-1] )  

  


g[i]分为两种情况:1. 长度为1        nums[i]

  

                            2. 长度大于1分为两种情况:a. nums[i] > 0          nums[i] * g[i-1] 

    

                                                                          b. nums[i] < 0          nums[i] * f[i-1] 

  

g[i] = min(nums[i] ,  nums[i] * f[i-1]  , nums[i] * g[i-1] )  

  

  nums[i]等于0并不影响结果,所以不用讨论