Painless
MaxProductOfThree
任意のトリプレット（P、Q、R）に対してA [P] * A [Q] * A [R]を最大化します。
タスク説明
N個の整数で構成される空でない配列Aが与えられます。 トリプレット（P、Q、R）の積は、A [P] * A [Q] * A [R]（0≤P<Q <R <N）に等しくなります。
たとえば、次のような配列A：
例
A [0] = -3
A [1] = 1
A [2] = 2
A [3] = -2
A [4] = 5
A [5] = 6
次のトリプレットの例が含まれています。
- （0、1、2）、積は-3 * 1 * 2 = -6
- （1、2、4）、積は1 * 2 * 5 = 10
- （2、4、5）、積は2 * 5 * 6 = 60
あなたの目標は、トリプレットの最大の積を見つけることです。
関数を書く：
class solution {public int solution(int [] A); }
空でない配列Aが与えられると、任意のトリプレットの最大積の値を返します。
たとえば、次のような配列Aが与えられます。
例
A [0] = -3
A [1] = 1
A [2] = 2
A [3] = -2
A [4] = 5
A [5] = 6
トリプレット（2、4、5）の積が最大であるため、関数は60を返す必要があります。
次の仮定のための効率的なアルゴリズムを記述します。
- Nは[3..100,000]の範囲内の整数です。
- 配列Aの各要素は、[-1,000..1,000]の範囲内の整数です。
解く
Program
MaxProductOfThreeSolution.java
public int solution(int[] A) {
int max1 = -9999;
int max2 = -9999;
int max3 = -9999;
int min2 = 9999;
int min1 = 9999;
for (int a : A) {
if (a > max1) {
max3 = max2;
max2 = max1;
max1 = a;
} else if (a > max2) {
max3 = max2;
max2 = a;
} else if (a > max3) {
max3 = a;
}
if (a < min1) {
min2 = min1;
min1 = a;
} else if (a < min2) {
min2 = a;
}
}
int maxProduct = max1 * max2 * max3;
if (max1 <= 0 || min1 >= 0) {
// 全て負 || 全て正
return maxProduct;
} else {
if (min2 < 0 ) {
// せめて2つ負
int temp = max1 * min1 * min2;
if (temp > maxProduct) return temp;
}
}
return maxProduct;
}
Detected time complexity:
O(N * log(N))
jUnit
MaxProductOfThreeSolutionTest.java