首页 > 代码库 > Maximum Product Subarray JAVA实现
Maximum Product Subarray JAVA实现
题目描述：
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.
分析：
这里主要得考虑两个因素：1、头元素到第一个0元素之间和两个0元素之间负数的个数；2、当遇到0时，应该重新计算当前的最大值
设计的思想：
1、本题为了更加方便，我使用了额外的空间，且空间复杂度为O（n）
2、第一个数组主要用来计算从头或者从0开始相乘的值，第二个数组是用来计算从头或者0后面第一个负数开始每个元素乘积。
例：（由于表达不好，上面可能解释的不是太清楚）
原始序列：
2 | 4 | -1 | 3 | 4 | 0 | 2 | -1 | 3 | -1 |
oneValue：
2 | 4 | -4 | -12 | -48 | 0 | 2 | -2 | -6 | 6 |
twoValue：
2 | 4 | -4 | 3 | 12 | 0 | 2 | -2 | 3 | -3 |
代码：
package com.edu.leetcode;import javax.xml.transform.Templates;public class MaximumProductSubarray { public int maxProducts(int[] A) { if(A.length==1){ //如果数组中只有一个元素直接输出 return A[0]; } int[] oneValues = new int[A.length]; //辅助空间1，记录从头或者从0开始到当前位置的乘积 int[] twoValues=new int[A.length]; //辅助空间2，从头或者从0开始遇到第一负数时，后面的值重新从当前位置开始 oneValues[0]=A[0]; twoValues[0]=A[0]; boolean first =true; //从头或者从0开始，判断是否遇到了负数 for(int i=1;i<A.length;i++){ if(oneValues[i-1]==0){ oneValues[i]=A[i]; twoValues[i]=A[i]; first=true; } else{ if(A[i-1]<=-1&&first){ //当前面的一个数是从头或者从0开始的第一个负数时，将twoValues[i]的值赋值为A[i] twoValues[i]=A[i]; oneValues[i]=oneValues[i-1]*A[i]; first=false; } else{ oneValues[i]=oneValues[i-1]*A[i]; twoValues[i]=twoValues[i-1]*A[i]; } } } int maxValue=http://www.mamicode.com/oneValues[0]; for(int i=0;i<oneValues.length;i++){ if(oneValues[i]>maxValue) maxValue=oneValues[i]; if(twoValues[i]>maxValue) maxValue=twoValues[i]; } return maxValue; } public static void main(String[] args) { // TODO Auto-generated method stub MaximumProductSubarray mps = new MaximumProductSubarray(); int[] s = {2,3,-1}; System.out.println(mps.maxProducts(s)); }}
Maximum Product Subarray JAVA实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。