动态规划6，最大数组和，环形子数组最大和，乘积最大子数组

最大子数组和

���路：

1.经验+题目要求

dp[i]表示：以 i 位置为结尾的所有子数组中的最大和

2.状态转移方程

按长度来划分，如果长度为1，那么dp[i] = nums[i];

如果长度大于1，那么当前位置的最大和就为 i-1 位置最大和 + 当前位置，dp[i] = dp[i-1] + nums[i];

然后每一次都要取他们两个中的最大值。

存在 dp[i-1] , 建表时候多建一格，dp[0]位置为0 就不影响后面的填表

4 .

从左往右填表。

class Solution {public:    int maxSubArray(vector& nums) {           int n = nums.size();           vector dp(n+1);                      int ret = INT_MIN;//为了不影响比较           for(int i = 1 ; i               dp[i] = max(nums[i-1],dp[i-1]+nums[i-1]);               ret = max(dp[i],ret);//找出dp表里面的最大值           }           return ret;    }};public:    int maxSubarraySumCircular(vector        int n = nums.size();        vector            f[i] = max(nums[i-1],f[i-1]+nums[i-1]);            ret1 = max(ret1,f[i]);            g[i] = min(nums[i-1],g[i-1]+nums[i-1]);            ret2 = min(ret2,g[i]);            num+=nums[i-1]; //求nums和        }        return num == ret2 ? ret1 : max(ret1,num - ret2);    }};public:    int maxProduct(vector        int n = nums.size();        vector           f[i] = max(nums[i-1],max(f[i-1]*nums[i-1], g[i-1]*nums[i-1]));           ret1 = max(f[i],ret1);           g[i] = min(nums[i-1],min(g[i-1]*nums[i-1], f[i-1]*nums[i-1]));           ret2 = min(g[i],ret2);        }        return ret1;    }};

h2乘积为正数的最长子数组长度/h2 pimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250422/-25042223155Q50.png" //pp思路：/p p1.经验+题目要求/p pdp[i]表示：以 i 位置为结尾的所有子数组中乘积为正数的最长长度。/p p2.状态转移方程/ppimg src="https://m.xiaogongju.com.cn/uploads/allimg/20250422/-25042223155V12.png" //pp首先细分，当长度为1的时候，如果nums[i] 0 ,则为1；/pp当长度为1的时候，如果nums[i] 0 的情况，f[i-1] + 1最次也为1，占主导；

对于nums[i]

就可以总结为下面那两种占主导的情况。

g[i] 也是如此。

3.

因为题目问的是长度，初始化f[0] = g[0] = 0;

4.从左往右，两个表一起填写。

class Solution {public:    int getMaxLen(vector& nums) {        int n = nums.size();        vector f(n+1);        auto g = f;        int ret = INT_MIN;        for(int i =1; i            if(nums[i-1]  0)            {                f[i] = f[i-1]+1;                g[i] = g[i-1] == 0 ? 0 : g[i-1]+1;            }            else if(nums[i-1]