【Leetcode】【Medium】Maximum Product Subarray
2024-09-04 16:19:49
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
.
解题思路:
求连续子串和/积系列,最优的方法是只遍历一遍,实现o(n)的时间复杂度。
思考:
1、对于子序列中连续的正数,那么乘积也是不断的累积,如果遇到了负数,则最大乘积值暂时为前面正数的累积;
如果按照这个思路,只需要记录连续正数乘积最高,即为最大子序列积;那么这样就实现了o(n)的复杂度;
2、但是上面思路忽略了子序列中包含两个负数,负负得正,依然可以成就最大子序列积;
针对这种情况,在遍历的时候,不仅记录乘积最大值,还记录乘积最小值,乘积最小值
最新文章
- C# 给PDF添加图片背景
- FMS 4中multicast脚本的小修正
- 在ASP.NET 5中读取配置文件
- mysql 常用配置
- MFC中,如何自定义用户消息
- AD采样问题总结
- XACML-<;Target>; 元素的结构与相关的评估
- linux下配置tomcat7 + solr4.9(续)--- 多核索引的配置
- 邮件协议POP3/IMAP/SMTP服务的区别
- W5300E01-ARM 交叉编译器(Cross Compiler)用户手册
- 用extundelete恢复rm -rf删的文件
- 暑假OI规划
- objectmapper使用
- PAT A1153 Decode Registration Card of PAT (25 分)——多种情况排序
- NOI2018退役记
- http和https的作用与区别
- cxPivotGrid导出数据
- hdu 3030
- 1491. [NOI2007]社交网络【最短路计数】
- OpenGl学习 glenable()函数理解