、Maximum Product Subarray
、Maximum Product Subarray
Tyan
发布于 2019-05-25 23:09:03
发布于 2019-05-25 23:09:03
1. 问题描述
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.
2. 求解
这个题跟Leetcode 53——Maximum Subarray类似，可以用三重循环，两种循环解决。但最好的还是用动态规划解决，找出状态转移方程最关键。由于乘积可能为负数，负负得正，因此第i-1次的乘积最大值（maxValuePre）与最小值（minValuePre）都需要保留。当然也可以定义最大值最小值数组来保存第i次乘积的最大值（maxValue）与最小值（minValue）。与Maximum Subarray相比，最大值为maxValue = max(minValuePre * nums[i], maxValuePre * nums[i], nums[i])，最小值同样如此。
没有定义最大值数组与最小值数组
public class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int maxValue = nums[0];
int minValue = nums[0];
int result = nums[0];
int maxValuePre = nums[0], minValuePre = nums[0];
for(int i = 1; i < n; i++) {
maxValue = Math.max(minValuePre * nums[i], Math.max(maxValuePre * nums[i], nums[i]));
minValue = Math.min(minValuePre * nums[i], Math.min(maxValuePre * nums[i], nums[i]));
if(maxValue > result) {
result = maxValue;
}
maxValuePre = maxValue;
minValuePre = minValue;
}
return result;
}
}定义最大值数组与最小值数组
public class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int maxValue[] = new int[nums.length];
int minValue[] = new int[nums.length];
maxValue[0] = nums[0];
minValue[0] = nums[0];
int result = nums[0];
for(int i = 1; i < n; i++) {
maxValue[i] = Math.max(minValue[i - 1] * nums[i], Math.max(maxValue[i - 1] * nums[i], nums[i]));
minValue[i] = Math.min(minValue[i - 1] * nums[i], Math.min(maxValue[i - 1] * nums[i], nums[i]));
if(maxValue[i] > result) {
result = maxValue[i];
}
}
return result;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年03月14日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录