首页 > 其他 > 详细

【LeetCode】152. Maximum Product Subarray

时间:2017-04-18 20:57:08      阅读:292      评论:0      收藏:0      [点我收藏+]

题目:  

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

题解:

  先暴力解,遍历所有组合,更新最大值。很显然得超时。

Solution 1 (TLE)

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

  Besides keeping track of the largest product, we also need to keep track of the smallest product. Why? The smallest product, which is the largest in the negative sense could become the maximum when being multiplied by a negative number. (from here)

  Let us denote that:

f(k) = Largest product subarray, from index 0 up to k.

   Similarly,

g(k) = Smallest product subarray, from index 0 up to k.

   Then,

f(k) = max( f(k-1) * A[k], A[k], g(k-1) * A[k] )
g(k) = min( g(k-1) * A[k], A[k], f(k-1) * A[k] )

Solution 2 ()

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int maxPro = nums[0], minPro = nums[0], result = nums[0], n = nums.size();
        for (int i=1; i<n; i++) {
            int mx = maxPro, mn = minPro;
            maxPro = max(max(nums[i], mx * nums[i]), mn * nums[i]);
            minPro = min(min(nums[i], mx * nums[i]), mn * nums[i]);
            result = max(maxPro, result);
        }
        return result;
    }
};

 

【LeetCode】152. Maximum Product Subarray

原文:http://www.cnblogs.com/Atanisi/p/6729865.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!