LeetCode <dp>152&628 Maximum Product Subarray

原创

大学里的混子

修改于 2018-11-15 14:53:20

5170

修改于 2018-11-15 14:53:20

文章被收录于专栏：LeetCode

152. Maximum Product Subarray

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

Example 1:

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

Example 2:

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

题目大意：找到一个连续的字数粗，使他们的乘积为最大值，返回这个最大值

解法：

思路：注意这里，要维护一个最大值和最小值，因为最小值可能为负数，我们知道，负负得正；

    public int maxProduct(int[] nums) {
        if (nums==null||nums.length ==0) return 0;
        int max = nums[0],min = nums[0],result = nums[0];
        for (int i=1;i<nums.length;i++){
            int temp = max;
            max = Math.max(Math.max(nums[i]*max,nums[i]*min),nums[i]) ;
            min = Math.min(Math.min(nums[i]*temp,nums[i]*min),nums[i]);
            if (result<max) result = max;
        }
        return result;
    }

628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

题目大意：在一个数组中找三个数，使得这三个数的乘积最大；

这个题目与LeetCode152有相似之处，由于题目没有说明是非负数，所以一定要负数考虑在范围内；

解法：

这个思路来自于，从一个数组中查找到第二大的值。我们采用同样的方法，得到数组中的第一大，第二大，第三大的数。

     public int maximumProduct(int[] nums) {
        int firstMax = Integer.MIN_VALUE;
        int secMax = firstMax,thirdMax = firstMax;
        int firstMin = Integer.MAX_VALUE;
        int secMin = firstMin;

        for (int i =0;i<nums.length;i++){
            if (nums[i]>firstMax){
                thirdMax = secMax;
                secMax = firstMax;
                firstMax = nums[i];
            }else {
                if (nums[i]>secMax){
                    thirdMax = secMax;
                    secMax = nums[i];
                }else {
                    if (nums[i]>thirdMax){
                        thirdMax = nums[i];
                    }
                }
            }

            if (nums[i]<firstMin){
                secMin = firstMin;
                firstMin = nums[i];
            }else {
                if (nums[i]<secMin){
                    secMin = nums[i];
                }
            }
        }
        return Math.max(firstMax*secMax*thirdMax,firstMax*firstMin*secMin);
    }

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度