Question: there is an array you need 3 multiplies inside the array that will bring the biggest sum of all.
For example, given the following input:
| Index | Value |
|---|---|
| 0 | -4 |
| 1 | 1 |
| 2 | -8 |
| 3 | 9 |
| 4 | 6 |
...the expected output is -4, -8, -9, as -4 * -8 * 9 == 288.
you can assume that there are no nulls inside the array.
signature must be public static int findTriplet(int[] a);.
my code:
public static int findTriplet(int[] a) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE,
maxLowby2 = Integer.MIN_VALUE, maxLowby1 = Integer.MIN_VALUE,
secondMin = Integer.MAX_VALUE, minIndex = -1, maxIndex = -1, indexofLowby1 = -1;
//we run a for loop to go over the array and collect all our needed information.
for (int i = 0; i < a.length; i ) {
//first we find the smallest value
if (min > a[i] && a[i] < 0) {
min = a[i];
minIndex = i;// we save the index so we can find other num that is negative and is different from this 1
////here we try to find the second smallest num in the array in such that it has to be a minus otherwise we wont be able to get a popsitive number(-1*-1=positive)
//if the index is different and second Min is smaller then the value in a[i] and a[i] must be a negetive num;
} else if (minIndex != i && secondMin > a[i] && a[i] < 0) {
secondMin = a[i];
}
//
if (max < a[i]) {
max = a[i];
maxIndex = i;
//now we look for only positive numbers
//here we need to find two other sumbers that are the biggest in the array but are different then each other.
} else if (max > a[i] && a[i] >= 0 && maxLowby1 < a[i] && maxIndex != i) {
maxLowby1 = a[i];
indexofLowby1 = i;
//here we find the last positive number that will be smaller the max and maxlowBy1
} else if (a[i] >= 0 && indexofLowby1 != i)
maxLowby2 = a[i];
}
// we creat the needed numbers and return the max value of them.
int finalMax = max * maxLowby2 * maxLowby1;
int secondMinus = max * min * secondMin;
return Math.max(finalMax, secondMinus);
} ```
CodePudding user response：
You can use:
import java.util.Arrays;
public class LargestMultiple {
private static void storeValues(
int new_value,
int[] values
)
{
int i = -1;
for (;i 1 < values.length && new_value > values[i 1]; i){}
if (i >= 0)
{
for (int j = 0; j < i; j)
{
values[j] = values[j 1];
}
values[i] = new_value;
}
}
public static int findTriplet(
int[] a
)
{
if (a.length == 0)
{
throw new IllegalArgumentException("Not enough values");
}
if (a.length <= 3)
{
int value = a[0];
for (int i = 1; i < a.length; i)
{
value *= a[i];
}
return value;
}
int[] maximums = {0, 0, 0};
int[] minimums = {0, 0};
int[] negatives = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
int num_positive = 0;
for (int i = 0; i < a.length; i )
{
if (a[i] < 0)
{
storeValues(-a[i], minimums);
storeValues(a[i], negatives);
}
else
{
storeValues(a[i], maximums);
num_positive ;
}
}
if (num_positive > 0)
{
return Math.max(
minimums[0] * minimums[1],
maximums[0] * maximums[1]
) * maximums[2];
}
else
{
return negatives[0] * negatives[1] * negatives[2];
}
}
public static void test(final int[] values)
{
System.out.println(
Arrays.toString(values)
" -> "
findTriplet(values)
);
}
public static void main(final String[] args)
{
test(new int[]{1});
test(new int[]{1, 2});
test(new int[]{1, 2, 3});
test(new int[]{1, 2, 3, 4});
test(new int[]{1, 2, -1, -2});
test(new int[]{1, 2, -1});
test(new int[]{1, 2, 3, -1});
test(new int[]{1, 2, 3, -1, -4});
test(new int[]{-1, -2, -3, -4});
}
}
Which outputs:
[1] -> 1 [1, 2] -> 2 [1, 2, 3] -> 6 [1, 2, 3, 4] -> 24 [1, 2, -1, -2] -> 4 [1, 2, -1] -> -2 [1, 2, 3, -1] -> 6 [1, 2, 3, -1, -4] -> 12 [-1, -2, -3, -4] -> -6
Note: Although storeValues is O(N) on the size of the array, it is always called from findTriplet with fixed-sized arrays then, from within that function, it will have a constant O(1) execution time.
CodePudding user response：
If you only need to keep track of three values it's pretty easy to avoid inner loops. Keep track of the positives and negatives separately. You'll only need to keep track of the two smallest negatives.
Compare each new number against the previously known values. By falling through you determine where to slide values down (in terms of absolute value) and insert the new one.
For the potential that there aren't at least three positive numbers in the list you'll also want to track the largest negatives (the one with smallest absolute value). This does assume there are at least three values in the list.
n1 = n2 = p1 = p2 = p3 = 0; // negatives/positives with largest abs()
a3 = a2 = a1 = int.minValue; // negatives with smallest abs() kept in ascending order
for(i = 0; i < a.length; i ) {
m = a[i];
if (m > p3) { p1 = p2; p2 = p3; p3 = m; }
else if (m > p2) { p1 = p2; p2 = m; }
else if (m > p1) { p1 = m; }
else if (m < n2) { n1 = n2; n2 = m; }
else if (m < n1) { n1 = m; }
if (m <= 0) {
if (m > a3) { a1 = a2; a2 = a3; a3 = m; }
else if (m > a2) { a1 = a2; a2 = m; }
else if (m > a1) { a1 = m; }
}
}
if (p3 == 0) { v = a1 * a2 * a3; }
else if (p2 == 0) { v = a1 * a2 * p3; }
else if (p1 == 0) { v = a1 * p2 * p3; }
else if (n1 * n2 > p2 * p3) { v = n1 * n2 * p3; }
else { v = p1 * p2 * p3; }
return v;
This definitely has some Java syntax errors. Consider it to be pseudocode.
I believe this Python version is producing correct results: https://www.online-python.com/kKliQYANh0
CodePudding user response：
If all numbers are less than 0, or only one number is less than 0, or the product of the two lowest numbers is less than the product of the second highest and the third highest number, then the result is the product of the 3 highest numbers. In any other case, the result is the product of the highest and the two lowest numbers.
public static int findTriplet(int[] a) {
//Remember - this function expects an array with exactly 5 values, none of which are 0!
Arrays.sort(a);
if(a[4] < 0 || a[1] > 0 || a[0] * a[1] < a[2] * a[3]) return a[2] * a[3] * a[4];
return a[0] * a[1] * a[4];
}