介绍家乡的网站怎么做,南京网站设计外包,青岛市城市建设管理局网站,凡科网站代码leetcode原题链接#xff1a;乘积最大子数组
题目描述 给你一个整数数组 nums #xff0c;请你找出数组中乘积最大的非空连续子数组#xff08;该子数组中至少包含一个数字#xff09;#xff0c;并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。子数组 是… leetcode原题链接乘积最大子数组
题目描述 给你一个整数数组 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-位 整数
解题方法动态规划。
1. 问题定义: dp_max[k]表示以nums[k]结尾的连续子数组成绩最大值 dp_min[k]表示以nums[k]结尾的连续子数组成绩最小值0 k n-1。
2. 初始化dp_max[0]dp_min[0]nums[0]。
3. 状态转移方程dp[k] std::max(dp_max[k-1]*nums[k], dp_min[k-1]*nums[k], nums[k])。
4. 结果返回计算并返回最大值max_result std::max(max_result, dp_max[i])。
C代码
#include iostream
#include vector
#include climitsclass Solution {
public:int maxProduct(std::vectorint nums) {int n nums.size();if (n 0) {return -1;}// 1. 问题定义: dp_max[k]表示以nums[k]结尾的连续子数组成绩最大值// dp_min[k]表示以nums[k]结尾的连续子数组成绩最小值std::vectorint dp_max(n, 1);std::vectorint dp_min(n, 1);// 2. 初始化dp_max[0] nums[0];dp_min[0] nums[0];// 3. 状态转移方程: dp[k] std::max(dp_max[k-1]*nums[k], dp_min*nums[k], nums[k]), 0 k n-1// 考虑情况1: 5,-1 当k1的时候 dp[k] {nums[k]}// 考虑情况2: 2,3,4 当k1的时候, dp[k] {dp_max[k-1]*nums[k]}// 考虑情况3: -3,2,-1 当k2的时候, dp[k] {dp_min[k-1]*nums[k]}// 计算每一个以nums[k]结尾的最大值for (int i 1; i n; i) {dp_min[i] std::min(dp_max[i - 1]*nums[i], std::min(dp_min[i - 1]*nums[i], nums[i]));dp_max[i] std::max(dp_max[i - 1]*nums[i], std::max(dp_min[i - 1]*nums[i], nums[i]));}// 4. 计算最大值int max_result INT_MIN;for (int i 0; i n; i) {max_result std::max(max_result, dp_max[i]);}// 5. 返回结果return max_result;}
};
