java中的最大乘积子数组 - 腾讯云开发者社区 - 腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

动态规划 —— 子数组系列-乘积最大子数组

乘积最大子数组题目链接： 152....乘积最大子数组 - 力扣（LeetCode） https://leetcode.cn/problems/maximum-product-subarray/description/ 2....算法原理状态表示：以某一个位置为结尾或者以某一个位置为起点 f[i]表示：以i位置为结尾的所有子树中的最大乘积 [i]表示：以i位置为结尾的所有子树中的最小乘积 2....填表顺序本题的填表顺序是：从左往右，两个表一起填 5. 返回值：题目要求 + 状态表示本题的返回值是：f表里的最大值 3....填表（填表方法：状态转移方程） //因为返回值是返回f表里的最大值，所以先定义一个变量记录一下最终结果 int ret=INT_MIN;//因为要求最大值，所以定义无穷小

801 0

一文看懂《子数组的最大乘积问题》

问题描述：给定一个长度为 N 的整数数组，只允许乘法，不能用除法。计算任意 N - 1 个数的组合中乘积最大的一组，并写出算法的时间复杂度。...我们假设被排除的元素索引为 i（0 <= i < N, 且 i 为整数）。我们用两个数组 l 和 r 分别记录从前和从后的子数组乘积。...我们用 l[i]表示原数组中从 0 开始到 i - 1(包括 i - 1)的乘积， r[i]表示原数组中从 i(包括 i)到 N - 1(包括 N - 1)的乘积。 ?...由于只需要从有到尾和从尾部到头扫描数组两次即可得到数组l和r，进而可以在线性的时间复杂度获取到所有的乘积，然后在这个过程中我们就可以取出最大值，因此这样做的时间复杂度为O(N)。...总结子数组乘积问题有很多变种问题，今天我们讲的就是其中一中类型，我们先通过朴素的解法，然后一步步分析问题的本质，通过空间换时间的解法进一步减少了时间复杂度。

1.4K1 0

您找到你想要的搜索结果了吗？

是的

没有找到

乘积最大子数组

题目给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。...示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。...解答首先假设存在某个最大乘积，然后对数组遍历，在经过每个元素的时候，有以下四种情况：如果该元素为正数：如果到上一个元素为止的最大乘积也是正数，那么直接乘上就好了，同样的最大乘积也会变得更大如果到上一个元素为止的最大乘积是负数...，那么最大乘积就会变成该元素本身，且连续性被断掉如果该元素为负数：如果到上一个元素为止的最大乘积也是负数，那么直接乘上就好了，同样的最大乘积也会变得更大如果到上一个元素为止的最大乘积是正数，那么最大乘积就会不变...，且连续性被断掉以上四种情况中说到的最大乘积都是临时最大乘积，每遍历新的元素都需要进行比较来确定真正的最大乘积。

4962 0

乘积最大子数组

题目: 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。...输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。...思路: 遍历数组时计算当前最大值，不断更新我们需要记录阶段子数组最大值和最小值,当出现负数的时候我们阶段最大值×负数会变成阶段最小值,阶段最小值×负数会变阶段最大值,因此我们需要存储阶段最小值,并且在需要负数的时候进行提取的交换...return nums[0]; } int max=nums[0],itemMax=nums[0],itemMin=nums[0]; //max 存储所有连续子数组最大值...//itemMax,itemMin存储当前子数组最大值和最小值 //其中需要itemMin存最小值主要因为数组里可能有负数,负数最小值再乘以一个整数就是最大值

6581 0

LeetCode：152_Maximum Product Subarray | 最大乘积连续子数组 | Medium

这道题属于动态规划的题型，之前常见的是Maximum SubArray，现在是Product Subarray，不过思想是一致的。...当然不用动态规划，常规方法也是可以做的，但是时间复杂度过高（TimeOut），像下面这种形式： 1 // 思路：用两个指针来指向字数组的头尾 2 int maxProduct(int A[], int...，也可能小，所以，对于相加的情况，只要能够处理局部最大和全局最大之间的关系即可，对此，写出转移方程式如下： local[i + 1] = Max(local[i] + A[i], A[i]); global...，和后面一个较大的负数相乘，得到的反而是一个较大的数，如{2，-3，-7}，所以，我们在处理乘法的时候，除了需要维护一个局部最大值，同时还要维护一个局部最小值，由此，可以写出如下的转移方程式： max_copy...，但是如何写出正确的方程式，需要我们不断的实践并总结才能达到。

5829 0

乘积小于k的连续子数组个数

和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。...示例 1：输入：nums = [10,5,2,6], k = 100 输出：8 解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、...需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。...right-left+1•此时left+1，并将总的乘积除以left位置的元素以保证此时left～right之间的元素乘积满足小于k的要求•每次满足要求后，left～right之间的次数都满足right-left...，并且包含left自己做子数组的时候 # 每次右指针位移到一个新位置，应该加上 x 种数组组合： # nums[right] #

4541 0

乘积最大子数组

题目描述解题思路代码复杂度分析 GitHub LeetCode 项目题目描述题目链接给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积...示例 1: 输入：[2,3,-2,4] 输出：6 解释：子数组 [2,3] 有最大乘积 6。...解题思路本题要求的是「乘积最大的子数组」，但是最大的乘积可能是两个正数相乘，也可能是两个负数相乘。定义 pi 为包含 i 的子数组最大乘积，ni 为包含 i 的子数组最小乘积。...则记数组 nums0:i 的最大乘积值为 m： pi = max(pi - 1 numsi, numsi, ni - 1 numsi) ni = min(pi - 1 numsi, numsi,...Java 编程思想-最全思维导图-GitHub 下载链接，需要的小伙伴可以自取~！！！

8471 0

数组中两元素的最大乘积

题目给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。...示例 1：输入：nums = [3,4,5,2] 输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4...示例 2：输入：nums = [1,5,4,5] 输出：16 解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。...解题找到数组最大的两个数，排序 O(nlogn) class Solution { public: int maxProduct(vector& nums) { sort

4043 0

数组中两元素的最大乘积

题目给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。...示例 1：输入：nums = [3,4,5,2] 输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4...示例 2：输入：nums = [1,5,4,5] 输出：16 解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。

2402 0

leetCode163|数组中两元素的最大乘积

一，数组中两元素的最大乘积 1，问题简述给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。...请你计算并返回该式的最大值。...示例 3：输入：nums = [3,7] 输出：12 提示： 2 <= nums.length <= 500 1 <= nums[i] <= 10^3 3，题解思路循环遍历数组的每一个元素...，计算前后元素的最大乘积，更新最大值 4，题解程序 public class MaxProductTest { public static void main(String[] args) {...，下意识就是想着利用暴力破解的方式进行解决一下，虽然时间复杂度为O(n^2)，但是个人觉得利用最简单的方式来解决一道问题还是比较值得的，不要低估每一个方法背后的价值，不要认为复杂度高的方法都是不好的 ?

4223 0

LeetCode-152-乘积最大子数组

# LeetCode-152-乘积最大子数组给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。...示例1：输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。...示例2：输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。...# 解题思路方法1、动态规划：遍历数组的时候不断计算当前的最大值同时还需要记录之前的最小值，当遍历的到的nums[i]为负数的时候最大值*负数：会导致最大值变为最小最小值*负数：会导致最小值变为最大...// dp_max[i] 指的是以第 i 个数结尾的乘积最大的连续子序列 // dp_min[i] 指的是以第 i 个数结尾的乘积最小的连续子序列

2592 0

数组中最大和的子数组

题目：输入一个整型数组，数据元素有正数也有负数，求元素组合成连续子数组之和最大的子数组，要求时间复杂度为O(n)。...例如：输入的数组为1, -2, 3, 10, -4, 7, 2, -5，最大和的连续子数组为3, 10, -4, 7, 2，其最大和为18。...由于本题在网络中广为流传，本题也顺利成为2006年程序员面试题中经典中的经典。分析：如果不考虑时间复杂度，我们可以枚举出所有子数组并求出他们的和。...= index_end = i; // 调整子数组最大和下标 } } } // 输出最大和的子数组及其开始、结束下标 printf("index_start: %d\nindex_end...源码参考推荐：子数组的最大和[算法] 微软、Google等面试题

8163 0

数组中两元素的最大乘积

题目给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (numsi-1)*(numsj-1) 取得最大值。请你计算并返回该式的最大值。...示例 1：输入：nums = [3,4,5,2] 输出：12 解释：如果选择下标 i=1 和 j=2（下标从 0 开始），则可以获得最大值，(nums[1]-1)*(nums[2]-1) = (4...示例 2：输入：nums = [1,5,4,5] 输出：16 解释：选择下标 i=1 和 j=3（下标从 0 开始），则可以获得最大值 (5-1)*(5-1) = 16 。

3342 0

LC152—乘积最大子数组

难度中等963 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。...示例 1: 输入: [2,3,-2,4] 输出: 6 解释: 子数组 [2,3] 有最大乘积 6。...示例 2: 输入: [-2,0,-1] 输出: 0 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组标签：动态规划遍历数组时计算当前最大值，不断更新令imax为当前最大值，则当前最大值为...imax = max(imax * nums[i], nums[i]) 由于存在负数，那么会导致最大的变最小的，最小的变最大的。

2291 0

子数组最小乘积的最大值（前缀和 + 单调栈）

题目一个数组的最小乘积定义为这个数组中最小值乘以数组的和。比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。...请注意，最小乘积的最大值考虑的是取余操作之前的结果。题目保证最小乘积的最大值在不取余的情况下可以用 64 位有符号整数保存。子数组定义为一个数组的连续部分。...示例 1：输入：nums = [1,2,3,2] 输出：14 解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。 2 * (2+3+2) = 2 * 7 = 14 。...示例 2：输入：nums = [2,3,3,1,2] 输出：18 解释：最小乘积的最大值由子数组 [3,3] （最小值是 3）得到。 3 * (3+3) = 3 * 6 = 18 。...示例 3：输入：nums = [3,1,5,6,4,2] 输出：60 解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。

7524 0

动态规划子数组系列一＞乘积最大子数组

621 0

连续子数组的最大和

题目描述题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)O(n)。...例如，输入的数组为 {1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为 {3, 10, -4, 7, 2}，因此输出为该子数组的和为 18....思路解析思路1 遍历所有子数组思路2 动态规划 F（i）：以arr[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变 F（i）=max(F（i-1）+arr[i] , arr[i])

9311 0

连续子数组的最大和

A[1],…,A[n-1], A[n])，这个数组有很多连续子数组，那么其中数组之和的最大值是什么呢？...子数组必须是连续的。...方法二：找规律思路思路如原书给出的如下表格，主要思想是：记录两个数，最大的子数组和+累加子数组和遍历数组，随时更新最大的子数组和一旦累加数为负数，直接放弃，将累加子数组和设置为0 ?...~ 拓展问题最大子矩阵问题给定一个矩阵（二维数组），其中数据有大有小，请找一个子矩阵，使得子矩阵的和最大，并输出这个和。...为了能够找出最大的子矩阵，我们需要考虑所有的情况。假设这个子矩阵是 2 * k, 也就是说它只有两行，要找出最大子矩阵，我们要从左到右不断的遍历才能找出在这种情况下的最大子矩阵。

9142 0

滑动窗口之乘积小于k的子数组

乘积小于k的子数组给定一个正整数数组 nums和整数 k 。请找出该数组内乘积小于 k 的连续的子数组的个数。...，k是指乘积需要小于的那个数，ans是指要求解的子数组的个数，l、r是指左右指针。...因为我们计算的是连续的子数组的个数，每次右指针移动、加入一个新的右边的数值的时候，在满足l到r的乘积小于k的前提下，总的ans的增加量就是新的值、新的值与之前所有可连续的值的组合，这个就用到一点点数学知识了...让我们来想一想，我们需要满足的条件是连续数组内的数乘积小于k，当右指针一直向右移动使得乘积不断增大时，总会有大于等于k的时候，那个时候，我们就需要改变l了，在这种情况下，我们计算的ans就不是现在的r-l...因为当l不变、r向右移动时，我们的乘积一直都是非递减的，如果当前右指针移动到的位置使得l到r不满足乘积小于k，那我们再继续移动右指针，乘积一定依旧不满足小于k，那就说明这个l我们已经“利用”完了，l可以退出滑动窗口了

7361 0

环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空子数组的最大可能和。环形数组意味着数组的末端将会与开头相连呈环状。...子数组最多只能包含固定缓冲区 nums 中的每个元素一次。...设数组长度为，下标从开始，在环形情况中，答案可能包括以下两种情况：构成最大子数组和的子数组为，包括到\ 共个元素，其中0≤i最大子数组和的子数组为和，其中 0<i<j<n。第一种情况的求解方法与求解普通数组的最大子数组和方法完全相同，读者可以参考53号题目的题解：最大子序和。...右端点坐标范围在的最大前缀和可以用表示，递推方程为：至此，我们可以使用以上方法求解出环形数组的最大子数组和。特别需要注意的是，本题要求子数组不能为空，我们需要在代码中做出相应的调整。

1571 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭