编程之美----子数组的最大乘积
問(wèn)題：給定一個(gè)長(zhǎng)度為N的整數(shù)數(shù)組，只允許用乘法，不能用除法，計(jì)算任意(N-1)個(gè)數(shù)的組合中乘積最大的一組，并寫(xiě)出算法的時(shí)間復(fù)雜度。
解法一：用一個(gè)數(shù)組保存從左邊到右邊前i個(gè)元素的乘積。用另一個(gè)數(shù)組保存從右邊到左邊N-i個(gè)元素的乘積。然后結(jié)果就為兩個(gè)數(shù)組中元素對(duì)應(yīng)的乘積，復(fù)雜度為o(N)。
解法二：設(shè)N個(gè)數(shù)的乘積為P，對(duì)P進(jìn)行分析。
1，P為0，則數(shù)組中至少包含一個(gè)0，假設(shè)除去一個(gè)0后，其它N-1個(gè)數(shù)的乘積為Q，若Q為0，則數(shù)組中至少有兩個(gè)0，則返回0.若Q為正數(shù)，返回Q。若Q為負(fù)數(shù)，返回0.
2，P為負(fù)數(shù)。掃描一遍數(shù)組，去掉絕對(duì)值最小的負(fù)數(shù)。
3，P為正數(shù)。若數(shù)組中存在正數(shù)值，那么去掉最小的正數(shù)值，否則去掉絕對(duì)值最大的負(fù)數(shù)值。
對(duì)于P的正負(fù)性判定，可不需要直接求乘積，而是掃描一遍數(shù)組，求出數(shù)組中正數(shù)、負(fù)數(shù)、和0的個(gè)數(shù)，從而判斷P的正負(fù)性，遍歷的同時(shí)求出絕對(duì)值最小的正數(shù)和負(fù)數(shù)，絕對(duì)值最大的正數(shù)和負(fù)數(shù)，復(fù)雜度為o(N).
轉(zhuǎn)載于:https://www.cnblogs.com/wen-ge/p/4127150.html
總結(jié)
以上是生活随笔為你收集整理的编程之美----子数组的最大乘积的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
