题解 | #连续子数组的最大乘积#

连续子数组的最大乘积

http://www.nowcoder.com/practice/abbec6a3779940aab2cc564b22d36859

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    //本题的思想为动态规划
    //定义一个一样长的node类型的dp数组
    //dp[i]有两个值,dp[i].max的含义为必须以nums[i]为结尾的情况下连续子数组的最大值
    //dp[i].min的含义为必须以nums[i]为结尾的情况下,连续子数组的最小值
    //为什么要求最小值,比如实例3,-2*-6的结果反而是最大的,这就是为什么要求最小值的原因
    //用一个变量res统计求dp数组的过程中出现的最大值即可
    struct node{
        int max;
        int min;
    };
    int max(int a,int b){
        return a>b?a:b;
    }
    int min(int a,int b){
        return a>b?b:a;
    }
    int maxProduct(vector<int>& nums) {
        // write code here
        if(nums.size()<=0)
            return 0;
        int n=nums.size();
        node dp[n];
        dp[0].max=nums[0];
        dp[0].min=nums[0];
        int res=dp[0].max;
        for(int i=1;i<n;i++){
            dp[i].max=max(max(nums[i]*dp[i-1].max,nums[i]*dp[i-1].min),nums[i]);
            dp[i].min=min(min(nums[i]*dp[i-1].max,nums[i]*dp[i-1].min),nums[i]);
            res=max(res, dp[i].max);
        }
        return res;
    }
};
全部评论

相关推荐

07-22 11:12
门头沟学院 Java
不是,我就随手投的怎么还真发面试啊
皮格吉:大厂特别快的——来自已经被共享中
点赞 评论 收藏
分享
程序员小白条:找的太晚,别人都是大三实习,然后大四秋招春招的,你大四下了才去实习,晚1年
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务