教育局两学一做网站,赛事竞猜网站开发,汽配外贸论坛,网站建设页面设计之后个人主页#xff1a;兜里有颗棉花糖 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 #x1f354;本专栏旨在提高自己算法能力的同时#xff0c;记录一下自己的学习过程#xff0c;希望… 个人主页兜里有颗棉花糖 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 本专栏旨在提高自己算法能力的同时记录一下自己的学习过程希望对大家有所帮助 希望我们一起努力、成长共同进步。 目录 1️⃣题目描述2️⃣题目解析3️⃣解题代码 1️⃣题目描述
给你一个整数数组 nums 请你找出数组中乘积最大的非空连续子数组该子数组中至少包含一个数字并返回该子数组所对应的乘积。
测试用例的答案是一个 32-位 整数。
子数组 是数组的连续子序列。
示例1 输入: nums [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。 示例2 输入: nums [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 注意
1 nums.length 2 * 104-10 nums[i] 10nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数
2️⃣题目解析
虽然本题目要求的是求取乘积最大子数组但是我们还得把乘积最小的情况求取出来。为什么呢因为不只是正数 * 正数 0还有负数 * 负数 正数的情况。
状态表示
f[i]表示以i位置为结尾的所有子数组的最大乘积g[i]表示以i位置为结尾的所有子数组的最小乘积
状态转移方程
f[i] max(max(nums[i],f[i - 1] * nums[i - 1]),g[i - 1] * nums[i - 1]);g[i] min(min(nums[i],f[i - 1] * nums[i - 1]),g[i - 1] * nums[i - 1]);
3️⃣解题代码
class Solution {
public:int maxProduct(vectorint nums) {int n nums.size();vectorint f(n1);auto g f;f[0] g[0] 1;int ret INT_MIN;for(int i 1;i n;i){int a nums[i - 1];int b f[i - 1] * nums[i - 1];int c g[i - 1] * nums[i - 1];f[i] max(max(a,b),c);g[i] min(min(a,b),c);ret max(ret,f[i]);}return ret;}
};通过啦
