微软面试题：求子数组最大乘积问题_求职面试_非技术区_程序员俱乐部

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

       最容易想到的就是通过一次遍历把所有（N-1）个数的组合找出来，分别计算他们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N的2次方）,显然这不是最好的解决办法。

       且看下面的实现方法，当然也是比较简单的，毕竟没太多时间思考，他的时间复杂度只有O(N)。

       当然肯定有其他的方式解决这个问题，blog友如果有好的方式可以贴出来分享。谢谢！
 

/**
 6 * @author Jack.Wang
 7 * @see ORATION: underline">http://jack2007.blogjava.net/
 8 */

{
10    private static final long serialVersionUID = 7799621696481440826L;
11
12    private static long maxOfSubArray(Array arr) {
13        // 最大值
14        long max = 0;
15        int size = arr.size();
16        // s[i]表示前i个元素的乘积,可知s[i]=s[i-1]*arr.get(i-1) 其中(1<=i<=N)
17        long[] s = new long[size + 1];
18        s[0] = 1;
19        // t[i]表示i后面元素的乘积，可知t[i]=t[i+1]*arr.get(i) 其中(1<=i<=N)
20        long[] t = new long[size + 1];
21        t[size] = 1;
22        // 设p[i]为除第i个元素之外的其他元素之积，即：p[i]=s[i-1]*t[i+1];
23        long[] p = new long[size + 1];
24
25        // 求出 s数组
26        for (int i = 1; i <= size; i++) {
27            s[i] = s[i - 1] * ((Integer) arr.get(i - 1));
28        }
29        // 求出t数组
30        for (int i = size - 1; i >= 0; i--) {
31            t[i] = t[i + 1] * ((Integer) arr.get(i));
32        }
33        // 计算 p数组
34        for (int i = 1; i <= size; i++) {
35            p[i] = s[i - 1] * t[i];
36            if (p[i] > max) {
37                max = p[i];
38            }
39        }
40        return max;
41    }
42
43    public static void main(String[] args) {
44        Array<Integer> array = new Array<Integer>();
45        array.add(1);
46        array.add(4);
47        array.add(6);
48        array.add(10);
49        array.add(12);
50        array.add(40);
51        // 上面的数字很简单,口算也知道N-1个最大乘积为115200
52        // 算法结果：
53        System.out.println(" 算法结果：" + maxOfSubArray(array));
54    }
55
56}