国产亚洲无线码一区二区 ,国产亚洲精品线观看动态图,亚洲日韩区在线电影

微軟面試題---求子數(shù)組最大乘積問(wèn)題

        給定一個(gè)長(zhǎng)度為N的整數(shù)數(shù)組，只允許用乘法，計(jì)算任意（N-1）個(gè)數(shù)的組合乘積中最大的一組，并
寫(xiě)出算法的時(shí)間復(fù)雜度。
       最容易想到的就是通過(guò)一次遍歷把所有（N-1）個(gè)數(shù)的組合找出來(lái)，分別計(jì)算他們的乘積，并比較
大小。由于總共有N個(gè)（N-1）個(gè)數(shù)的組合，總的時(shí)間復(fù)雜度為O（N的2次方）,顯然這不是最好的解決
辦法。
       且看下面的實(shí)現(xiàn)方法，當(dāng)然也是比較簡(jiǎn)單的，畢竟沒(méi)太多時(shí)間思考，他的時(shí)間復(fù)雜度只有O(N)。
       當(dāng)然肯定有其他的方式解決這個(gè)問(wèn)題，blog友如果有好的方式可以貼出來(lái)分享。謝謝！

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個(gè)元素的乘積,可知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

// 設(shè)p[i]為除第i個(gè)元素之外的其他元素之積，即：p[i]=s[i-1]*t[i+1];
23

long[] p = new long[size + 1];
24

// 求出 s數(shù)組
26

for (int i = 1; i <= size; i++) {
27

s[i] = s[i - 1] * ((Integer) arr.get(i - 1));
28

}
29

// 求出t數(shù)組
30

for (int i = size - 1; i >= 0; i--) {
31

t[i] = t[i + 1] * ((Integer) arr.get(i));
32

}
33

// 計(jì)算 p數(shù)組
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

// 上面的數(shù)字很簡(jiǎn)單,口算也知道N-1個(gè)最大乘積為115200
52

// 算法結(jié)果：
53

System.out.println(" 算法結(jié)果：" + maxOfSubArray(array));
54

}
55

}
57

本博客為學(xué)習(xí)交流用，凡未注明引用的均為本人作品，轉(zhuǎn)載請(qǐng)注明出處，如有版權(quán)問(wèn)題請(qǐng)及時(shí)通知。由于博客時(shí)間倉(cāng)促，錯(cuò)誤之處敬請(qǐng)諒解，有任何意見(jiàn)可給我留言，愿共同學(xué)習(xí)進(jìn)步。

posted on 2008-10-17 12:43 Jack.Wang 閱讀(4806) 評(píng)論(11) 編輯收藏所屬分類(lèi): 數(shù)學(xué)&算法

Feedback

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 13:33 wpf

這個(gè) ，從 n個(gè)數(shù)據(jù)中找到最小的一個(gè)，剩下的乘積最大，不就行了，當(dāng)然，為正數(shù)的情況下回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 14:17 Jack.Wang

@wpf
恩是的，可以分為三種情況：正數(shù)，負(fù)數(shù)，和零進(jìn)行分析，全為正數(shù)時(shí)，除去最小的那個(gè)，剩下的乘積就是最大的！當(dāng)然其他情況也可進(jìn)一步分析，也是一個(gè)不錯(cuò)的解決方式。復(fù)雜度也是big O N,等我把這種方式補(bǔ)上！謝謝！回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 17:00 Eric Jiang

整數(shù)當(dāng)然應(yīng)該不能排除負(fù)數(shù)和零的情況。
把所有數(shù)乘起來(lái)，分別再整除每個(gè)數(shù)，保留最大的。回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 17:06 YYX

@Eric Jiang
關(guān)鍵不可能把所有數(shù)乘起來(lái)，除非你借用BigDecimal之類(lèi)的類(lèi) 回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 17:55 ZelluX

@YYX
n個(gè)數(shù)乘起來(lái)不可能做到，n-1個(gè)數(shù)就可以了？回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 20:05 Jack.Wang

@YYX
確實(shí)存在溢出問(wèn)題，基本上那種算法都會(huì)涉及到多數(shù)相乘，所以用 bigdecimal 表述數(shù)字是需要的！回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-17 20:59 小亮Web

難等結(jié)果回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題[未登錄](méi) 2008-10-17 22:27 ol_soft

@wpf
同意啊回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-18 03:55 ZelluX

其實(shí)壓根就不用乘法吧。。。回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-18 16:41 wpf

這個(gè)是不是沒(méi)要求最后乘法的結(jié)果，只要得到n-1分別是那些就好了吧，呵呵
這樣基本上不用考慮溢出的情況回復(fù) 更多評(píng)論

# re: 微軟面試題---求子數(shù)組最大乘積問(wèn)題 2008-10-22 18:28 stonebow

一次遍歷，如果遇到兩個(gè)零就不用算了；然后分別記錄最小正數(shù)和最大負(fù)數(shù)和最小負(fù)數(shù)。盡量保證所選數(shù)里有偶數(shù)個(gè)負(fù)數(shù)，如果為奇數(shù)個(gè)的話(huà)就用里面的絕對(duì)值最小的負(fù)數(shù)換外面絕對(duì)值最大的正數(shù)，或用絕對(duì)值最小的正數(shù)換外面絕對(duì)值最大的負(fù)數(shù)。只要有一個(gè)正數(shù)就沒(méi)問(wèn)題，如果都是負(fù)數(shù)就要看N的奇偶性了。反正一次遍歷總能找到這些數(shù)，然后可以根據(jù)判斷條件得出答案回復(fù) 更多評(píng)論

新用戶(hù)注冊(cè) 刷新評(píng)論列表


只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。




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

走在架構(gòu)師的大道上 Jack.Wang's home

公告

留言簿(26)

我參與的團(tuán)隊(duì)

隨筆分類(lèi)(232)

隨筆檔案(190)

我的鄰居們

積分與排名

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

Feedback