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

2021年9月21日 3点热度 0条评论 来源: Tom Hardy

题目描述

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

题目分析

这时一个很典型的动态规划题目,数组不一定是有序的,而且连续子序列中的符号也不一定一致,这是两点需要注意的,详细思路请见源代码。

源代码

class Solution {
public:
    int maxProduct(vector<int>& nums) 
    {
        if(nums.empty()) return 0;
        int ret, pos, neg;
        pos = nums[0];
        neg = nums[0];
        ret = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            int temp = pos;
            //最大值乘以负数有可能变为最小值,最小值乘以负数有可能变为最大值
            pos = max(nums[i], max(pos * nums[i], neg * nums[i]));//在不断的计算最大值
            neg = min(nums[i], min(temp * nums[i], neg * nums[i]));//在不断的计算最小值
            ret = max(pos, ret);
        }
        return ret;
    }
};

    原文作者:Tom Hardy
    原文地址: https://blog.csdn.net/qq_29462849/article/details/96842992
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。