LeetCode 动态规划之乘积最大子数组

简介: LeetCode 动态规划之乘积最大子数组

题目


乘积最大子数组


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


测试用例的答案是一个 32-位 整数。


子数组 是数组的连续子序列。


示例 1:


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


示例 2:


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


提示:


1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数


题解


解题分析


题解思路


  1. 该题是一个典型的动态规划题目;


  1. 我们需要不断的去遍历数组,获取最大值 maxF = Math.max(mx * nums[i], nums[i]);


  1. 由于数组中存在负数,可能导致最大的值变为最小值,最小值变为最大值。因此还需要维护当前的最小值


minF = Math.min(mn * nums[i], nums[i]); 4. 如果负数出现的时候 ,min, max 进行交换再进行下一步计算;


复杂度分析


  • 时间复杂度:O(N)


  • 空间复杂度:O(1)


解题代码


题解代码如下(代码中有详细的注释说明):


class Solution {
    public int maxProduct(int[] nums) {
        // maxF 最大值, minF 最小值, ans 结果
        int maxF = nums[0], minF = nums[0], ans = nums[0];
        // 数组长度
        int len = nums.length;
        for (int i =1; i < len; i++) {
            // 保存旧数据
            int mx = maxF , mn = minF;
            // 更新最大值
            maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));
            // 更新最小值
            minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));
            // 更新结果
            ans = Math.max(maxF, ans);
        }
        // 返回
        return ans;
    }
}


提交后反馈结果:


image.png


参考信息



相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
45 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
4月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
125 2
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
4月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
24 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
25 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
70 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
19 0