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.

题目大意： 求出最大连续子数组乘积。

解题思路 —— 暴力求解

直接将所有的存在可能都求解出来，找出最大值。

AC代码

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // products[i]: i...当前位置的乘积
        vector<int> products(nums.size(), 0);
        int  ans = INT_MIN;
        for(size_t j = 0; j < nums.size(); ++j)
        {
            for(int i = j; i >= 0; --i)
            {
                if(i == j) products[i] = nums[i];
                else products[i] = products[i]*nums[j];

                // 保存最大乘积
                ans = max(ans, products[i]);
            }
        }

        return ans;
    }
};