53.最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
🙆♂️思路：
aaaaa,我老不会这个题
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
时间复杂度：O(n)
int maxSubArray(int* nums, int numsSize){ int sum = nums[0]; for(int i = 1;i < numsSize;i++) { if(nums[i-1] > 0) { nums[i] += nums[i-1]; } if(nums[i] > sum) sum = nums[i]; } return sum; }
152.乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
先解决完上面那个题，下面这个题思路很容易固化
比如直接判断 上一个数据和当前数据同号则相乘，不然则舍弃 这是一种错误🙅的想法💡
比如[-4,-5,2,-6,-7] 很明显全部数字之积才是结果！
而不是当40*-6时候舍去！
🙆思路：
转移方程应该是
maxDP[i + 1] = max(maxDP[i] * A[i + 1], A[i + 1],minDP[i] * A[i + 1])
minDP[i + 1] = min(minDP[i] * A[i + 1], A[i + 1],maxDP[i] * A[i + 1])
dp[i + 1] = max(dp[i], maxDP[i + 1])
因为我们记录📝前面的最大值和最小值，当与当前数值乘完后，可能最大值变成最小值，最小值变成最大值。
int max_num(int a,int b,int c) { if(a >= b && a >= c) return a; else if(b >= a && b >= c) return b; else if(c >= a && c >= b) return c; else return 0; } int min_num(int a,int b,int c) { if(a <= b && a <= c) return a; else if(b <= a && b <= c) return b; else if(c <= a && c <= b) return c; else return 0; } int maxProduct(int* nums, int numsSize){ if(numsSize == 0) return 0; int zjl_max = nums[0]; int zjl_min = nums[0]; int mht_max = nums[0]; for(int i = 1;i < numsSize;i++) { int temp = zjl_max; zjl_max = max_num(zjl_max*nums[i],zjl_min*nums[i],nums[i]); zjl_min = min_num(temp*nums[i],zjl_min*nums[i],nums[i]); if(mht_max < zjl_max) mht_max = zjl_max; //这是一种错误想法，由上一题很容易影响 但是我没有提交～ 直接记录提醒自己 /* if(nums[i-1] * nums[i] > 0) //同号 { nums[i] *= nums[i-1]; } if(nums[i] > sum) { sum = nums[i]; } */ } return mht_max; }
整理代码
int min(int a, int b) {return a > b ? b : a;} int max(int a, int b) {return a > b ? a : b;} int maxProduct(int* nums, int numsSize){ int ans = nums[0]; int dp_mi[numsSize + 5]; int dp_ma[numsSize + 5]; dp_ma[0] = dp_mi[0] = nums[0]; for (int i = 1; i < numsSize; ++i) { dp_mi[i] = min(nums[i], min(nums[i] * dp_mi[i - 1], nums[i] * dp_ma[i - 1])); dp_ma[i] = max(nums[i], max(nums[i] * dp_mi[i - 1], nums[i] * dp_ma[i - 1])); ans = max(ans, dp_ma[i]); } return ans; }
