Maximum Product Subarray
2024-03-26 23:07:08
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example
For example, given the array [2,3,-2,4], the contiguous subarray[2,3] has the largest product = 6.
分析：
因为这题要求乘积最大，而负数和负数相乘可是是正数，所以，我们必须得保存两个变量，即当到达A[i]时，前一个数A[i - 1]所对应的最大值和最小值max[i - 1] 和 min[i - 1]. max[i] 和min[i]和这些值有如下关系：
min[i] = min(nums[i], min[i - 1] * nums[i], max[i - 1] * nums[i]);
max[i] = max(nums[i], min[i - 1] * nums[i], max[i - 1] * nums[i]);
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
* cnblogs.com/beiyeqingteng/
*/
public int maxProduct(int[] nums) {
if (nums == null || nums.length == ) return ;
if (nums.length == ) return nums[];
int[] min = new int[nums.length];
int[] max = new int[nums.length];
min[] = nums[];
max[] = nums[];
for (int i = ; i < nums.length; i++) {
min[i] = min(nums[i], min[i - ] * nums[i], max[i - ] * nums[i]);
max[i] = max(nums[i], min[i - ] * nums[i], max[i - ] * nums[i]);
}
int tempMax = max[];
for (int i = ; i < max.length; i++) {
if (tempMax < max[i]) {
tempMax = max[i];
}
}
return tempMax;
}
public int max(int a, int b, int c) {
return Math.max(a, Math.max(b, c));
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
更简洁的做法：
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
* cnblogs.com/beiyeqingteng/
*/
public int maxProduct(int[] nums) {
if (nums == null || nums.length == ) return ;
if (nums.length == ) return nums[];
int pre_temp_min = nums[];
int pre_temp_max = nums[];
int global_max = nums[];
for (int i = ; i < nums.length; i++) {
int temp_min = min(nums[i], pre_temp_min * nums[i], pre_temp_max * nums[i]);
int temp_max = max(nums[i], pre_temp_min * nums[i], pre_temp_max * nums[i]);
pre_temp_min = temp_min;
pre_temp_max = temp_max;
global_max = Math.max(global_max, temp_max);
}
return global_max;
}
public int max(int a, int b, int c) {
return Math.max(a, Math.max(b, c));
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}
转载请注明出处：cnblogs.com/beiyeqingteng/
最新文章
- CNN 入门学习资料整理
- 【java】：通用小知识
- poj3642 01背包
- smarty初始化文件
- 李洪强经典iOS面试题11
- 【转】C++ 智能指针详解
- Speech Module
- hdu_5927_Auxiliary Set(xjb搞)
- Python学习的个人笔记（基础语法）
- PHP+Mysql基于事务处理实现转账功能的方法
- response.writeHead
- node(基础)_node.js中的http服务以及模板引擎的渲染
- Uva 11178 Morley定理
- PHP数组和字符串的处理函数汇总
- 让Netbeans 8.0 支持 Python 编程
- 我的php.ini上传文件配置
- IP数据报格式和IP地址路由
- 深入了解java虚拟机（JVM） 第十章 字节码指令
- springboot启动正常，访问restController报404
- 一致性hash与CRUSH算法总结