Find the maximum product that can be formed by taking any one element from each sub-array
The problem you post can be solved with a simple algorithm. We just need to keep tracking the maximum/minimum when iterating over each sub-array. We can keep finding the next maximum/minimum by multiplying the current maximum/minimum with the max/min value in each sub-array. We pick the maximum when the iterating is over. Its time complexity is O(n)
where n
is total number of elements in an array (i.e. sum of number of elements in each sub-array).
Here's the complete code. find_maximum_product
function keeps tracking the minimum/maximum and returns the maximum eventually, and it also keeps tracking the multipliers and return it:
/**
* arr: array of any number of sub-arrays and
* any number of elements in each sub-array.
* e.g. [[1, -1], [2, 3], [10, -100, 20]]
*/
function find_maximum_product(arr) {
let max = 1;
let min = 1;
let max_multipliers = [];
let min_multipliers = [];
for (let i = 0; i < arr.length; i++) {
const a = Math.max(...arr[i]);
const b = Math.min(...arr[i]);
const candidates = [max * a, max * b, min * a, min * b];
max = Math.max(...candidates);
min = Math.min(...candidates);
let new_max_multipliers;
let new_min_multipliers;
switch (max) {
case candidates[0]:
new_max_multipliers = max_multipliers.concat(a);
break;
case candidates[1]:
new_max_multipliers = max_multipliers.concat(b);
break;
case candidates[2]:
new_max_multipliers = min_multipliers.concat(a);
break;
case candidates[3]:
new_max_multipliers = min_multipliers.concat(b);
break;
}
switch (min) {
case candidates[0]:
new_min_multipliers = max_multipliers.concat(a);
break;
case candidates[1]:
new_min_multipliers = max_multipliers.concat(b);
break;
case candidates[2]:
new_min_multipliers = min_multipliers.concat(a);
break;
case candidates[3]:
new_min_multipliers = min_multipliers.concat(b);
break;
}
max_multipliers = new_max_multipliers;
min_multipliers = new_min_multipliers;
}
if (max >= min) {
return [max, max_multipliers];
}
return [min, min_multipliers];
}
const arrays = [
[
[-3, -4],
[1, 2, -3],
],
[
[1, -1],
[2, 3],
[10, -100, 20],
],
[
[-3, -15],
[-3, -7],
[-5, 1, -2, -7],
],
[
[14, 2],
[0, -16],
[-12, -16],
],
[
[-20, -4, -19, -18],
[0, -15, -10],
[-13, 4],
],
[
[-2, -15, -12, -8, -16],
[-4, -15, -7],
[-10, -5],
],
];
for (let i = 0; i < arrays.length; i++) {
const [max, max_multipliers] = find_maximum_product(arrays[i]);
console.log('Array:', JSON.stringify(arrays[i]));
console.log('Result:', `${max_multipliers.join(' * ')} = ${max}`);
console.log('');
}
UPDATE
Simpler version for just getting the maximum, not getting the multipliers:
/**
* arr: array of any number of sub-arrays and
* any number of elements in each sub-array.
* e.g. [[1, -1], [2, 3], [10, -100, 20]]
*/
function get_maximum_product(arr) {
return arr
.map((a) => [Math.min(...a), Math.max(...a)])
.reduce(
(acc, current) => {
const candidates = [
acc[0] * current[0],
acc[0] * current[1],
acc[1] * current[0],
acc[1] * current[1],
];
return [Math.min(...candidates), Math.max(...candidates)];
},
[1, 1]
)[1];
}
Here is a top-down recurrence that could be adapted to bottom-up (a loop) and utilises O(n)
search space.
Until I can complete it, the reader is encouraged to add a third return value in the tuple, largest_non_positive
for that special case.
// Returns [highest positive, lowest negative]
// Does not address highest non-positive
function f(A, i){
const high = Math.max(...A[i]);
const low = Math.min(...A[i]);
if (i == 0){
if (low < 0 && high >= 0)
return [high, low];
if (low <= 0 && high <= 0)
return [-Infinity, low];
if (low >= 0 && high >= 0)
return [high, Infinity];
}
const [pos, neg] = f(A, i - 1);
function maybeZero(prod){
return isNaN(prod) ? 0 : prod;
}
let hp = maybeZero(high * pos);
let hn = maybeZero(high * neg);
let ln = maybeZero(low * neg);
let lp = maybeZero(low * pos);
if (low < 0 && high >= 0)
return [Math.max(hp, ln), Math.min(hn, lp)];
if (low <= 0 && high <= 0)
return [ln, lp];
if (low >= 0 && high >= 0)
return [hp, hn];
}
var As = [
[[-3,-4], [1,2,-3]],
[[1,-1], [2,3], [10,-100,20]],
[[-3,-15], [-3,-7], [-5,1,-2,-7]],
[[-11,-6], [-20,-20], [18,-4], [-20,1]],
[[-1000,1], [-1,1], [-1,1], [-1,1]],
[[14,2], [0,-16], [-12,-16]],
[[-20, -4, -19, -18], [0, -15, -10],[-13, 4]]
];
for (let A of As){
console.log(JSON.stringify(A));
console.log(f(A, A.length - 1)[0]);
console.log('');
}