Leetcode53/152—最大子数组和/最大子数组乘积（状态转移方程/不熟）

101 阅读 0 评论 67 点赞

我是靠谱客的博主无辜哑铃，最近开发中收集的这篇文章主要介绍Leetcode53/152—最大子数组和/最大子数组乘积（状态转移方程/不熟），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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;
}