走在架構師的大道上 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友如果有好的方式可以貼出來分享。謝謝！

package org.blogjava.arithmetic;
2

import java.util.ArrayList;
4

/**
6

* @author Jack.Wang
7

* @see http://jack2007.blogjava.net/
8

*/
9

public class Array<E> extends ArrayList<E> {
10

private static final long serialVersionUID = 7799621696481440826L;
11

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

// 求出 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

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

}
57

本博客為學習交流用，凡未注明引用的均為本人作品，轉載請注明出處，如有版權問題請及時通知。由于博客時間倉促，錯誤之處敬請諒解，有任何意見可給我留言，愿共同學習進步。

posted on 2008-10-17 12:43 Jack.Wang 閱讀(4806) 評論(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的奇偶性了。反正一次遍歷總能找到這些數，然后可以根據判斷條件得出答案回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 計算字符串相似度的簡易算法微軟面試題---階乘問題微軟面試題---求子數組最大乘積問題微軟面試題---求出1的個數之小解 Java中對HashMap的深度分析與比較（轉載初學者筆記）為什么HashCode對于對象是如此的重要?

走在架構師的大道上 Jack.Wang's home

公告

留言簿(26)

我參與的團隊

隨筆分類(232)

隨筆檔案(190)

我的鄰居們

積分與排名

最新評論

閱讀排行榜

評論排行榜

Feedback