子数组的最大乘积

问题描述

　　给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意(N-1)个数的组合乘积中最大的一组，并写出算法的时间复杂度。

　　我们把所有可能的(N-1)个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个(N-1)个数的组合，总的时间复杂度为O(N²)，但显然这不是最好的解法。

分析与解法

【解法一】时间复杂度为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
     
      =0;i--){21             t[i]=t[i+1]*a[i+1];22         }23         long max = s[0]*t[0];24         for(i=0;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
     
      0){19                 if(minPositive==0)20                     minPositive=a[i];21                 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