首页 > 编程语言 > 详细

微软面试题: LeetCode 152. 乘积最大子数组 出现次数:2

时间:2021-04-12 15:21:39      阅读:20      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 解析:参考 LeetCode 评论区 liweiwei1419 大神的题解

https://leetcode-cn.com/problems/maximum-product-subarray/solution/dong-tai-gui-hua-li-jie-wu-hou-xiao-xing-by-liweiw/

使用 二维 dp 数组定义状态  

时间:O(n)  空间O(n)

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 class Solution {
 4 public:
 5     int maxProduct(vector<int>& nums)
 6     {
 7         //定义状态 dp[i][0]  以nums[i]结尾的乘积最大的子序列的乘积
 8         //定义状态 dp[i][1]  以nums[i]结尾的乘积最小的子序列的乘积
 9         vector<vector<int> > dp(2,vector<int>(nums.size()));
10         //状态初始化 dp[i][0]、dp[i][1]都初始化为nums[i],对应子序列只包含 nums[i]一个元素
11         dp[0] = nums;
12         dp[1] = nums;
13         int res = dp[0][0];
14         for(int i = 1; i < nums.size();++i)
15         {
16             if(nums[i] > 0)
17             {
18                 dp[i][0] = max(nums[i],nums[i] * dp[i-1][0]);
19                 dp[i][1] = max(nums[i],nums[i] * dp[i-1][1]);
20             }
21             else if(nums[i] < 0)
22             {
23                 dp[i][0] = max(nums[i],nums[i] * dp[i-1][1]);
24                 dp[i][1] = max(nums[i],nums[i] * dp[i-1][0]);
25             }
26             else
27             {
28                 dp[i][0] = 0;
29                 dp[i][1] = 0;
30             }
31             res = max(res,dp[i][0]);
32         }
33         return res;
34     }
35 };

由于后一次状态的更新只用到了前一次的状态,可以对二维的状态数组压缩,使用两个变量表示

dp_1 表示    以前一个元素 nums[i-1] 结尾的乘积最大的子序列的乘积

dp_12表示    以前一个元素 nums[i-1] 结尾的乘积最小的子序列的乘积

时间:O(n)  空间O(1)

代码如下:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 class Solution {
 4 public:
 5     int maxProduct(vector<int>& nums)
 6     {
 7         int dp_1 = nums[0];
 8         int dp_2 = nums[0];
 9         int res = nums[0];
10         for(int i = 1; i < nums.size();++i)
11         {
12             if(nums[i] > 0)
13             {
14                 dp_1 = max(nums[i],nums[i] * dp_1);
15                 dp_2 = min(nums[i],nums[i] * dp_2);
16             }
17             else if(nums[i] < 0)
18             {
19                 int dp_1_tmp = dp_1;
20                 dp_1 = max(nums[i],nums[i] * dp_2);
21                 dp_2 = min(nums[i],nums[i] * dp_1_tmp);
22             }
23             else
24             {
25                 dp_1 = 0;
26                 dp_2 = 0;
27             }
28             res = max(res,dp_1);
29         }
30         return res;
31     }
32 };

 

微软面试题: LeetCode 152. 乘积最大子数组 出现次数:2

原文:https://www.cnblogs.com/wangxf2019/p/14647461.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!