leetcode 152. 乘积最大子数组

题目详情

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

• 示例 1:
  输入: [2,3,-2,4]
  输出: 6
  解释: 子数组 [2,3] 有最大乘积 6。
• 示例 2:
  输入: [-2,0,-1]
  输出: 0
  解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

我的代码

class Solution {
public:vector<int> array;int getMax(int start, int end) {if (start == end) {return array[start];}int count = 0, res = 1;for (int i = start; i <= end; ++i) {if (array[i] < 0) {++count;}res *= array[i];}if (count % 2 == 0) {return res;} else {int temp1 = res, temp2 = res;for (int i = start; i <= end; ++i) {temp1 /= array[i];if (array[i] < 0) {break;}}for (int i = end; i >= start; --i) {temp2 /= array[i];if (array[i] < 0) {break;}}return max(temp1, temp2);}}int maxProduct(vector<int>& nums) {if (nums.size() == 1) {return nums[0];}array = nums;int res = array[0];int start = 0, end = 0;for (end = 0; end < array.size(); ++end) {if (array[end] == 0) {res = max(res, 0);if (end >= 1) {res = max(res, getMax(start, end - 1));}start = end + 1;}}if (start < end) {res = max(res, getMax(start, end - 1));}return res;}
};

我的成绩

执行结果：通过
执行用时 : 4 ms, 在所有 C++ 提交中击败了95.21%的用户
内存消耗 : 12.1 MB, 在所有 C++ 提交中击败了6.25%的用户

一些想法

本道题需要注意的是数组中的0，0是一个分界点，我的想法是遍历数组，当遇到为0的元素时，则计算前一部分数组中的最大值，计算方法为将前一部分内的所有元素相乘，然后计算前一部分的负数个数是否为复数，如果是复数，则直接返回计算值，否则，则除以第一个负数前的所有数，或是除以最后一个负数后的所有数，取两者的最大值。

执行用时为 0 ms 的范例

class Solution {
public:int maxProduct(vector<int>& nums) {int maxx = -9999999, imax = 1, imin = 1;for(int i=0; i<nums.size(); i++){if(nums[i] < 0){ int tmp = imax;imax = imin;imin = tmp;}imax = max(imax*nums[i], nums[i]);imin = min(imin*nums[i], nums[i]);maxx = max(maxx, imax);}return maxx;}
};

思考

范例用了动态规划，但我不知道怎么用。。。