子数组的最大乘积
问题描述
给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意(N-1)个数的组合乘积中最大的一组，并写出算法的时间复杂度。
我们把所有可能的(N-1)个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个(N-1)个数的组合，总的时间复杂度为O(N2)，但显然这不是最好的解法。
分析与解法
【解法一】时间复杂度为O(N)
具体代码如下：
1 package chapter2shuzizhimei.maxmutiply; 2 /** 3 * 子数组的最大乘积 4 * 【解法一】 5 * @author DELL 6 * 7 */ 8 public class MaxMutiply1 { 9 //寻找乘积的最大值 10 public static long findMax(long a[]){ 11 int n = a.length,i; 12 long[] s = new long[n]; //s[i]为第i个之前元素的乘积 13 s[0] = 1; 14 long[] t = new long[n]; //t[i]为第i个之后元素的乘积 15 t[n-1] = 1; 16 long[] p = new long[n]; //p[i]为数组除第i个元素外，其他N-1个元素的乘积 17 for(i=1;i<n;i++){ 18 s[i]=s[i-1]*a[i-1]; 19 } 20 for(i=n-2;i>=0;i--){ 21 t[i]=t[i+1]*a[i+1]; 22 } 23 long max = s[0]*t[0]; 24 for(i=0;i<n;i++){ 25 p[i] = s[i]*t[i]; 26 if(p[i]>max) 27 max = p[i]; 28 } 29 return max; 30 } 31 public static void main(String[] args) { 32 long a[] = {1,-2,3,5}; 33 System.out.println("最大乘积为："+findMax(a)); 34 35 } 36 37 }
程序运行结果如下：
最大乘积为：15
【解法二】
为了避免溢出，不直接求乘积，而是返回要剔除的那个数组元素，代码如下：
1 package chapter2shuzizhimei.maxmutiply; 2 3 /** 4 * 子数组的最大乘积 5 * 【解法二】 6 * @author DELL 7 * 8 */ 9 public class MaxMutiply2 { 10 //寻找乘积最大时应该剔除的元素 11 public static void findMax(long a[]){ 12 int negative = 0; //存放负数个数 13 int zero = 0; //存放零个数 14 long minPositive = 0; //最小正数 15 long minNegative = 0; //绝对值最小负数，即最大的负数 16 int n = a.length,i; 17 for(i=0;i<n;i++){ 18 if(a[i]>0){ 19 if(minPositive==0) 20 minPositive=a[i]; 21 else if(a[i]<minPositive) 22 minPositive=a[i]; 23 } 24 else if(a[i]==0){ 25 zero++; 26 } 27 else{ 28 negative++; 29 if(minNegative==0) 30 minNegative=a[i]; 31 else if(a[i]>minNegative) 32 minNegative=a[i]; 33 } 34 } 35 if(zero>=2){ 36 System.out.println("任意去掉一个元素就行，最大乘积为0!"); 37 return; 38 } 39 if(zero==1){ 40 if(negative%2==0){ 41 System.out.println("乘积最大时应该剔除的元素为：0"); 42 return; 43 } 44 else{ 45 System.out.println("任意去掉一个非0元素就行，最大乘积为0!"); 46 return; 47 } 48 } 49 if(negative%2!=0){ 50 System.out.println("乘积最大时应该剔除的元素为："+minNegative); 51 return; 52 } 53 else{ 54 System.out.println("乘积最大时应该剔除的元素为："+minPositive); 55 return; 56 } 57 } 58 public static void main(String[] args) { 59 long a[] = {1,-2,3,5,0,-1}; 60 findMax(a); 61 62 } 63 64 }
程序运行结果如下：
乘积最大时应该剔除的元素为：0