走在架构师的大道上 Jack.Wang's home

Java, C++, linux c, C#.net 技术,软件架构,领域建模,IT 项目管理 Dict.CN 在线词典, 英语学习, 在线翻译

BlogJava 首页 新随笔 联系 聚合 管理
  195 Posts :: 3 Stories :: 728 Comments :: 0 Trackbacks
微软面试题---求子数组最大乘积问题
        给定一个长度为N的整数数组，只允许用乘法，计算任意（N-1）个数的组合乘积中最大的一组，并
写出算法的时间复杂度。
       最容易想到的就是通过一次遍历把所有（N-1）个数的组合找出来，分别计算他们的乘积，并比较
大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N的2次方）,显然这不是最好的解决
办法。
       且看下面的实现方法，当然也是比较简单的，毕竟没太多时间思考，他的时间复杂度只有O(N)。
       当然肯定有其他的方式解决这个问题，blog友如果有好的方式可以贴出来分享。谢谢！
 
 1package org.blogjava.arithmetic;
 2
 3import java.util.ArrayList;
 4
 5/**
 6 * @author Jack.Wang
 7 * @see http://jack2007.blogjava.net/
 8 */
 9public class Array<E> extends ArrayList<E> {
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}
57



本博客为学习交流用，凡未注明引用的均为本人作品，转载请注明出处，如有版权问题请及时通知。由于博客时间仓促，错误之处敬请谅解，有任何意见可给我留言，愿共同学习进步。
posted on 2008-10-17 12:43 Jack.Wang 阅读(4789) 评论(11)  编辑  收藏 所属分类: 数学&算法

Feedback

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 13:33 wpf
这个 ，从 n个数据中找到最小的一个，剩下的乘积最大，不就行了，当然，为正数的情况下  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 14:17 Jack.Wang
@wpf
恩是的，可以分为三种情况：正数，负数，和零进行分析，全为正数时，除去最小的那个，剩下的乘积就是最大的！当然其他情况也可进一步分析，也是一个不错的解决方式。复杂度也是big O N,等我把这种方式补上！谢谢！  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 17:00 Eric Jiang
整数当然应该不能排除负数和零的情况。
把所有数乘起来，分别再整除每个数，保留最大的。  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 17:06 YYX
@Eric Jiang
关键不可能把所有数乘起来，除非你借用BigDecimal之类的类  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 17:55 ZelluX
@YYX
n个数乘起来不可能做到，n-1个数就可以了？  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 20:05 Jack.Wang
@YYX
确实存在溢出问题，基本上那种算法都会涉及到多数相乘，所以用 bigdecimal 表述数字是需要的！  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-17 20:59 小亮Web
难 等结果  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题[未登录] 2008-10-17 22:27 ol_soft
@wpf
同意啊  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-18 03:55 ZelluX
其实压根就不用乘法吧。。。  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-18 16:41 wpf
这个是不是没要求最后乘法的结果，只要得到n-1分别是那些就好了吧，呵呵
这样基本上不用考虑溢出的情况  回复  更多评论
  

# re: 微软面试题---求子数组最大乘积问题 2008-10-22 18:28 stonebow
一次遍历，如果遇到两个零就不用算了；然后分别记录最小正数和最大负数和最小负数。尽量保证所选数里有偶数个负数，如果为奇数个的话就用里面的绝对值最小的负数换外面绝对值最大的正数，或用绝对值最小的正数换外面绝对值最大的负数。只要有一个正数就没问题，如果都是负数就要看N的奇偶性了。反正一次遍历总能找到这些数，然后可以根据判断条件得出答案  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: