leetcode 152. 乘积最大子数组「贪心」「动态规划」

最新推荐文章于 2025-03-04 11:25:18 发布

Suryxin.

最新推荐文章于 2025-03-04 11:25:18 发布

阅读量1.1k

点赞数 10

文章标签： leetcode 动态规划算法贪心

本文链接：https://blog.csdn.net/weixin_51216553/article/details/140218417

版权

152. 乘积最大子数组

题目描述：

给你一个整数数组nums，请你找出数组中乘积最大的非空连续子数组，并返回该子数组所对应的乘积

思路1：贪心

由于 $n u m s [i]$ 都是整数，所以多乘一些数肯定不会让绝对值变小，所以我们就要尽可能多乘一些数

首先，我们考虑最简单的例子，也就是不包含0的情况：

统计负数的数量，如果是偶数，那直接返回所有数的乘积即可
如果负数的数量是奇数，我们就考虑删掉一个负数，由于我们上面说过，多乘一些数不会让乘积的绝对值变小，所以我们要尽可能少删数，从左往右找到第一个，下标为id1，从右往左找到第一个，下标为id2，要么是删id1往左的所有数，要么是删id2往右的所有数，两种情况取最大值就行
你可能会怀疑，为什么答案不可能是被删除的那一段，因为被删除的那一段都在另一半计算过了，删id1往左的所有数时，这段在计算删id2往右的所有数时，被计算过了

class Solution {
   
public:
    int fuck(int l, int r, vector<int>nums){
   
        if(l > r || l < 0 || r >= nums.size())return -2e9;
        if(l == r)return nums[l];
        int mul = 1;
        for(int i = l; i <= r; ++i)
            mul *= (nums[i] > 0 ? 1 : -1);
        if(mul > 0){
   
            for(int i = l; i <= r; ++i)mul *= nums[i];
            return mul;
        }
        mul = -1;
        int id1 = -1, id2 = -1;
        for(int i = l; i <= r; ++i){
   
            mul *= (nums[i] > 0 ? 1 : -1);
            if(mul > 0){
   
                id1 = i;
                break;
            }
        }
        int ans1 = 1, ans2 = 1;
        for(int i = id1 + 1; i <= r; ++i){
   
            ans1 *= nums[i];
        }
        mul = -1;
        for(int i = r; i >= l; --i){
   
            mul