问题描述:
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4]
,
the contiguous subarray [2,3]
has the largest product = 6
.
原问题链接:https://leetcode.com/problems/maximum-product-subarray/
问题分析
这个问题在之前的文章里有过讨论。对于一个连续最大子序列的乘积来说,它满足这么一个条件。这个最大值要么就是这个元素本身,要么就是它当前最大乘积和它的乘积,要么就是它当前最小乘积和它的乘积。因为这个元素为正数的时候,它和最大序列的乘积可能是最大的。而它为负数的时候,它和最小序列的乘积可能是最大的。
按照这个思路,我们可以得到详细的实现如下:
public class Solution { public int maxProduct(int[] nums) { int maxCur = nums[0], minCur = nums[0], maxTmp = maxCur, minTmp = minCur, result = nums[0]; for(int i = 1; i < nums.length; i++) { maxTmp = Math.max(nums[i], Math.max(maxCur * nums[i], minCur * nums[i])); minTmp = Math.min(nums[i], Math.min(maxCur * nums[i], minCur * nums[i])); maxCur = maxTmp; minCur = minTmp; result = Math.max(result, maxCur); } return result; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
java lru leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 ...LeetCode ...LeetCode ...Subarray 55 Jump Game 56 Merge Intervals 64 Minimum Path Sum 73
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: ...#53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先队列 #23:Merge k Sorted Lists
leetcode:leetcode刷题
leetcode双人赛 1. Pattern: Sliding Window,滑动窗口类型 滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始,一直往右边...
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题