Javascript - Optimal way to get maximum sum of arrays in an array

Question

I have the following array:

   arr = [
     [ 1, 1, 1, 1, 1, 1, 1 ],
     [ 1, 1, 0, 0, 1, 1, 0 ],
     [ 1, 0, 0, 0, 1, 0, 0 ],
     [ 0, 0, 0, 0, 0, 0, 0 ],
     [ 0, 1, 0, 1, 0, 0, 2 ],
     [ 1, 0, 0, 1, 0, 2, 4 ],
     [ 0, 0, 0, 0, 2, 4, 4 ],
     [ 0, 0, 0, 0, 4, 4, 0 ],
     [ 1, 1, 1, 0, 0, 0, 0 ],
     [ 1, 1, 0, 2, 0, 0, 2 ],
     [ 1, 0, 0, 4, 0, 2, 0 ],
     [ 0, 0, 0, 4, 2, 0, 0 ],
     [ 0, 0, 2, 0, 0, 0, 1 ],
     [ 0, 2, 4, 0, 0, 1, 2 ],
     [ 2, 4, 4, 2, 1, 2, 4 ],
     [ 4, 4, 0, 0, 2, 4, 0 ]
  ]

Currently, I'm getting the max array sum in arr i.e 19 like this

   function getMaxSum(arr) {
      return arr.map(e => e.reduce((a, b) => a + b, 0)).sort((a,b) => a - b)[arr.length - 1];
   }

I need to know is there any better way to achieve this?
I'm using array length of the original array to get the last element of resulting array because in this case, length of original array and resulting array is same. If the scenario is different then how can I use the length of the resulting array here:

return arr.map(e => e.reduce((a, b) => a + b, 0)).sort((a,b) => a - b)[HERE - 1];

What "cost" the most is the sort().

Hearner
– Hearner

2018-08-06 09:18:00 +00:00
Commented Aug 6, 2018 at 9:18 — Hearner
– Hearner, Commented Aug 6, 2018 at 9:18

OliverRadini · Accepted Answer · 2018-08-06 09:30:41Z

4

Not a huge improvement, but it seems a little more literal to spread the values into Math.max

const data = [
     [ 1, 1, 1, 1, 1, 1, 1 ],
     [ 1, 1, 0, 0, 1, 1, 0 ],
     [ 1, 0, 0, 0, 1, 0, 0 ],
     [ 0, 0, 0, 0, 0, 0, 0 ],
     [ 0, 1, 0, 1, 0, 0, 2 ],
     [ 1, 0, 0, 1, 0, 2, 4 ],
     [ 0, 0, 0, 0, 2, 4, 4 ],
     [ 0, 0, 0, 0, 4, 4, 0 ],
     [ 1, 1, 1, 0, 0, 0, 0 ],
     [ 1, 1, 0, 2, 0, 0, 2 ],
     [ 1, 0, 0, 4, 0, 2, 0 ],
     [ 0, 0, 0, 4, 2, 0, 0 ],
     [ 0, 0, 2, 0, 0, 0, 1 ],
     [ 0, 2, 4, 0, 0, 1, 2 ],
     [ 2, 4, 4, 2, 1, 2, 4 ],
     [ 4, 4, 0, 0, 2, 4, 0 ]
  ]

function getMaxSum(arr) {
  return Math.max(...arr.map(e => e.reduce((a, b) => a + b, 0)))
}

console.log(getMaxSum(data))

As @Rajesh points out, Math.max is faster that a sort:

const numbers = Array(10000).fill().map((x,i)=>i);

const max = numbersIn => Math.max(...numbersIn);
const getMaxViaSort = numbersIn => numbersIn
  .sort((a, b) => a > b ? -1 : 1)[0]

console.time('max');
max(numbers);
console.timeEnd('max');

console.time('max via sort');
getMaxViaSort(numbers);
console.timeEnd('max via sort');

edited Aug 6, 2018 at 9:30

answered Aug 6, 2018 at 9:17

OliverRadini

6,4941 gold badge26 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Rajesh Dixit Over a year ago

Actually, Math.max is way faster than using a loop. So it should have significant boast. Also, Array.sort is expensive, avoiding that will also help a lot

OliverRadini Over a year ago

Thanks, that's really good to know; I've updated my answer to illustrate that

Abdul Rafay Over a year ago

Thanks for the response and reminding me about Math.max. I've upvoted your answer. I'll be glad if you could help me with my second point too. :)

OliverRadini Over a year ago

Do you mean return arr.map(e => e.reduce((a, b) => a + b, 0)).sort((a,b) => a - b)[HERE - 1];?

Abdul Rafay Over a year ago

yes. I just need to know if it's possible to use resulting array length in this line.

|

Emil S. Jørgensen · Accepted Answer · 2018-08-06 09:55:17Z

2

The optimal strategy should be one where we need the least interaction with the arrays.

In my method i test the array products individually and compare that with a variable inside my loop. In this way i don't need to run a new implied loop to have Math.max check all my entries again, netting a speed boost.

This also saves on memory management as i don't need to map and return a new array of results for Math.max.

At the end of the loop i simply return the variable.

var data = [
    [1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 0, 1, 1, 0],
    [1, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0, 0, 2],
    [1, 0, 0, 1, 0, 2, 4],
    [0, 0, 0, 0, 2, 4, 4],
    [0, 0, 0, 0, 4, 4, 0],
    [1, 1, 1, 0, 0, 0, 0],
    [1, 1, 0, 2, 0, 0, 2],
    [1, 0, 0, 4, 0, 2, 0],
    [0, 0, 0, 4, 2, 0, 0],
    [0, 0, 2, 0, 0, 0, 1],
    [0, 2, 4, 0, 0, 1, 2],
    [2, 4, 4, 2, 1, 2, 4],
    [4, 4, 0, 0, 2, 4, 0]
];
function getMaxSum1(arr) {
    //The original method
    return arr.map(function (e) { return e.reduce(function (a, b) { return a + b; }, 0); }).sort(function (a, b) { return a - b; })[arr.length - 1];
}
function getMaxSum2(arr) {
    //From https://stackoverflow.com/a/51704254/5242739
    return Math.max.apply(Math, arr.map(function (e) { return e.reduce(function (a, b) { return a + b; }, 0); }));
}
function sumArray(arr) {
    var val = 0;
    for (var index = 0; index < arr.length; index++) {
        val += val;
    }
    return val;
}
function getMaxSum3(arr) {
    //My method
    var max;
    for (var i = 0; i < arr.length; i++) {
        var val = sumArray(arr[i]);
        if (max === void 0 || val > max) {
            max = val;
        }
    }
    return max;
}
//TEST
//parameters
var runs = 10;
var tests = 100000;
//output area
var out = document.body.appendChild(document.createElement("pre"));
//test functions
function simulate1() {
    var t = tests;
    var dt = Date.now();
    while (t--) {
        getMaxSum1(data);
    }
    out.textContent += 'getMaxSum1 took: ' + (Date.now() - dt) + "ms\n";
    requestAnimationFrame(simulate2);
}
function simulate2() {
    var t = tests;
    var dt = Date.now();
    while (t--) {
        getMaxSum2(data);
    }
    out.textContent += 'getMaxSum2 took: ' + (Date.now() - dt) + "ms\n";
    requestAnimationFrame(simulate3);
}
function simulate3() {
    var t = tests;
    var dt = Date.now();
    while (t--) {
        getMaxSum3(data);
    }
    out.textContent += 'getMaxSum3 took: ' + (Date.now() - dt) + "ms\n\n";
    if (runs--) {
        requestAnimationFrame(simulate1);
    }
}
//start
simulate1();

pre {
  max-height: 200px;
  overflow-y: scroll;
  background-color: #eee;
}

I included OliverRadini's answer to compare the relative speed boosts.

edited Aug 6, 2018 at 9:55

answered Aug 6, 2018 at 9:44

Emil S. Jørgensen

6,3891 gold badge17 silver badges30 bronze badges

8 Comments

Abdul Rafay Over a year ago

Thanks man. That's perfect. Upvoted it, Any help for my second point would be appreciated as well. :)

Emil S. Jørgensen Over a year ago

@AbdulRafay As i understood your second point, it sorts the list of products and returns the last element, which would be the biggest. Isn't this redundant if you already have the biggest result?

Abdul Rafay Over a year ago

I just need to know if it's possible to use resulting array length in this line: return arr.map(e => e.reduce((a, b) => a + b, 0)).sort((a,b) => a - b)[HERE - 1];

Emil S. Jørgensen Over a year ago

@AbdulRafay The array should be of the same length, so yes that will work in your example

Abdul Rafay Over a year ago

asking for the scenario of different length. I'm guessing the answer is that you cannot access resulting array length here, but I wanted to double check.

|

Collectives™ on Stack Overflow

Javascript - Optimal way to get maximum sum of arrays in an array

2 Answers 2

8 Comments

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

8 Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related