int の配列 が与えられた場合arrayofints、3 つの整数から得られる最大の積 を見つけますHighestproduct。入力 int の配列には、常に少なくとも 3 つの整数が含まれます。
そこで、 から 3 つの数字を取り出してarrayofints貼り付けましたhighestproduct。
Highestproduct = arrayofints[:2]
for item in arrayofints[3:]:
If min(Highestproduct) < item:
Highestproduct[highestproduct.index(min(Highestproduct))] = item
min項目が小さい場合highestproduct: 最小の数字を現在の数字に置き換えます。
これで最高の積が得られますが、どうやらもっと良い解決策があるようです。私のアプローチの何が間違っているのでしょうか? 私の解決策は O(n) でしょうか?
ベストアンサー1
2 つの最小要素と 3 つの最大要素を追跡すると、答えはmin1 * min2 * max1または になりますmax1 * max2 * max3。
3 つの int の最大積を得るには、最大要素を 3 つ選択する必要があります。ただし、最大要素 3 つのうちの最小の 2 つを最小 int 2 つに置き換えることができるという落とし穴があります。最小の int が両方とも負の場合、積は正になるため、( とは配列の最大要素 3 つのうちの最小の 2 つ)min1 * min2よりも大きくなる可能性があります。max2 * max3max2max3
これはO(n)時間内に実行されます。