【从0到1冲刺蓝桥杯国赛】每日一练——乘积最大子数组

成绩最大子数组https://leetcode-cn.com/problems/maximum-product-subarray/

题目描述： 

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 

思路分析： 

求最大子数组，子数组中可以有负数，有两个负数就可以，而且负数越大，再出现负数的时候乘积就越大。 

 C++实现：

class Solution {public:    int maxProduct(vector& nums) { vector maxF(nums), minF(nums); for(int i = 1; i<nums.size(); i++){     maxF[i] = max(maxF[i - 1] * nums[i], max(nums[i], minF[i - 1] * nums[i]));     minF[i] = min(minF[i - 1] * nums[i], min(nums[i], maxF[i - 1] * nums[i])); } return *max_element(maxF.begin(), maxF.end());    }};

滚动数组： 

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