152. 乘积最大子数组

Difficulty: 中等

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

1
2
3

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

1
2
3

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

image-20210827161936106

Solution

Language: ****

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //子数组必须连续
        //子数组乘积要考虑正负数
        int res = -9999999,mi = 1,ma=1;
        for(int i=0;i<nums.size();++i) {
            if (nums[i] < 0)
            {
                swap(ma,mi);
            }
            mi = min(mi * nums[i],nums[i]);
            ma = max(ma * nums[i],nums[i] );
            res = max(res ,ma);

        }
        return res;
    }
};

题目链接 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int nums[N];
int main(void) {
    int n;
    cin>>n;
    for(int i=0;i<n;i++) {
        cin>> nums[i];
    }
    int min_state = nums[0];
    int max_state = nums[0];
    int res_max=-999999;
    for(int i=1;i<n;i++) {
        int pre_low = min_state;
        min_state = min(pre_low * nums[i],min(nums[i],max_state* nums[i]));
        max_state = max(max_state*nums[i],max(nums[i],pre_low*nums[i]));
        res_max = max(res_max,max_state);
    }   
    cout << max(res_max,nums[0]) <<endl;
    
    return 0;
}