乘积最大子序列

问题描述

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-product-subarray

思路

• 首先对特殊情况，num.size()==0||num.size()==1进行处理。如果nums为空，返回0；如果只有一个数，返回那个唯一的数即可。
• 当num.size()>=2时，初始化max=-∞，i从2开始，递增到n结束，j从i开始，递增到n结束。如此循环可以得出以nums[i]为开始的所有子序列的乘积。当子序列的乘积大于最大值时，令最大值等于子序列的乘积即可。

题解

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