北京推广营销_网络工程适合女生吗_郑州外语网站建站优化_百度一下百度搜索

AC截图

题目

代码

时间复杂度为O(N^2)

class Solution {
public:int maxProduct(vector<int>& nums) {vector<int> dp(nums.size());for(int i=0;i<nums.size();i++){dp[i] = nums[i];}for(int i=1;i<nums.size();i++){if(nums[i]==1 && nums[i-1]==1){dp[i] = dp[i-1];continue;}int tmp = 1;for(int j=i;j>=0;j--){tmp *= nums[j];dp[i] = max(dp[i],tmp);}}int m=INT_MIN;for(int i=0;i<dp.size();i++){if(dp[i]>m){m = dp[i];}}return m;}
};

优化思路&代码

因为求的是连续子数组乘积，所以只用mx和mn来维护当前连续子序列的最大值和最小值即可。

如果nums[i]为负数，则需要交换mx和mn的值，因为最大值乘以一个负数会变成最小值，最小值乘以一个负数会变为最大值

class Solution {
public:int maxProduct(vector<int>& nums) {int mx=nums[0],mn=nums[0],res=nums[0];for(int i=1;i<nums.size();i++){if(nums[i]<0){swap(mx,mn);}mx = max(nums[i],nums[i]*mx);mn = min(nums[i],nums[i]*mn);res = max(mx,res);}return res;}
};