2.14 子数组的最大乘积

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

 

解题思路：本题比较能简单。典型的用空间换时间的方法。用A[x]表示a[1]*a[2]*...*a[x]，B[x]表示a[x]*a[x+1]*...*a[n]。一次遍历即可。O(n)

 

扩展：若本题可用除法？

 

解题思路：更简单了。A表示所有数的乘积，枚举不选的那个数就行。O(n)