[算法]LeetCode 152:乘积最大子序列
2024-09-06 09:53:14
题目描述:
给定一个整数数组 nums ,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题目思路:
还是动态规划的问题。
设置dp[nums.length][2]
dp[i][0]表示必须包含第i个数值,前面这一段区间的乘积最大值。
dp[i][1]表示必须包含第i个数值,前面这一段区间的乘积最小值。
状态转移方程:
dp[i][0] = Math.max(Math.max(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]), nums[i]);
dp[i][1] = Math.min(Math.min(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]), nums[i]);
题目代码:
public int maxProduct(int[] nums) {
int[][] dp = new int[nums.length][2];
dp[0][0] = nums[0];//最大值
dp[0][1] = nums[0];//最小值
int max = nums[0]; for (int i = 1; i < nums.length; i++) {
dp[i][0] = Math.max(Math.max(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]), nums[i]);
dp[i][1] = Math.min(Math.min(dp[i - 1][0] * nums[i], dp[i - 1][1] * nums[i]), nums[i]);
if(dp[i][0] > max) {
max = dp[i][0];
}
}
return max;
}
这代码还可以进一步优化,使得空间复杂度更小,因为每次值依赖上一次的结果,所以数组的行数只设为2即可。
public int maxProduct(int[] nums) {
int[][] dp = new int[2][2];
dp[0][0] = nums[0];//最大值
dp[0][1] = nums[0];//最小值
int max = nums[0]; for (int i = 1; i < nums.length; i++) {
dp[i % 2][0] = Math.max(Math.max(dp[(i - 1) % 2][0] * nums[i], dp[(i - 1) % 2][1] * nums[i]), nums[i]);
dp[i % 2][1] = Math.min(Math.min(dp[(i - 1) % 2][0] * nums[i], dp[(i - 1) % 2][1] * nums[i]), nums[i]);
if(dp[i % 2][0] > max) {
max = dp[i % 2][0];
}
}
return max;
}
最新文章
- 菜鸟学Struts2——Actions
- Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)D Dense Subsequence
- linux块设备驱动之实例
- AES加密补位填充的一个问题
- php版本历史
- app打包流程
- Hadoop集群系类文章
- js发送post请求下载文件
- Python collections模块总结
- 基于C#的BarCode 39实现
- ASP.NET学习笔记 —— 一般处理程序之图片上传
- Windows下的命令神器Cmder
- 一条命令解决mac版本python IDLE无法输入中文问题
- 【java提高】---HashSet 与TreeSet和LinkedHashSet的区别
- java基础之Number
- Linux下解包/打包,压缩/解压命令
- 跟我学SharePoint 2013视频培训课程——理解SharePoint网站的体系结构(3)
- C# user32.dll
- android事件分发
- 4.26-python学习笔记(变量及命名、字符串、格式化字符串print,format,%...)