152. Maximum Product Subarray

发表于 | 分类于

每日一题 2019 - 05 - 14

题目：

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

1
2
3
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

1
2
3
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

解法：

这个题让找出给定序列中连续序列的最大乘积，由于正数负数会交替出现，所以就设置两个数字 m、n 分别保存当前位置与之前位置相乘得到的最大最小数字，每次都迭代更新这两个数字，最后从 m 与 res 中找出最大指，即可；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int m = nums[0] ;
        int n = nums[0] ;
        int res = nums[0] ;
        for(int i = 1 ; i < nums.size() ; i ++ )
        {
            int first = m * nums[i] ;
            int second = n * nums[i] ;
            m = max(max(first,second),nums[i]);
            n = min(min(first,second),nums[i]);
            res = max(m,res);
        }
        return res ;
    }
};
0%
undefined