How accelerate reduce and forEach method?

Question

I wrote a program to count sum of range of array items, but still can not pass the quiz because my code is slow: Execution Timed Out (12000 ms). How can I speed up my code to pass the quiz?

function maxSum(arr, range) {
  let result = -Infinity
  range.forEach(el => {
    let sumArr = arr.slice(el[0],el[1]+1).reduce((a,b) => a+b)
    sumArr > result && (result = sumArr)
  })
  console.log(result)
return result 
}
maxSum([1,-2,3,4,-5,-4,3,2,1],[[0,8],[1,3],[0,4],[6,8]])

Your snippets takes some milliseconds. So... If you want help with the "12000 ms" code than post it... — Andreas
– Andreas, Commented Jun 23, 2020 at 14:31
arr.slice creates a copy of the array so maybe you don't want to do that. — Felix Kling
– Felix Kling, Commented Jun 23, 2020 at 14:31
I think one method to speed it up may be to remove subsets from the equation. For example, all [1,3], [0,4] and [6,8] are in [0,8]. Therefore sum [0,8] is maximum and you only need to calculate it. — Ambu
– Ambu, Commented Jun 23, 2020 at 14:33

pretzelhammer · Accepted Answer · 2020-06-23 14:36:13Z

2

Here's a faster and simpler solution. Iterates over range just once and collects all the sum totals, then maps it into sum ranges, then returns the max:

function maxSum(arr, range) {
  let left = [0];
  let total = 0;
  
  for (let num of arr) {
    left.push(total += num);
  }

  let sums = range.map(([a, b]) => left[b + 1] - left[a]);
  
  let result = Math.max(...sums);
  console.log(result);
  return result;
}

maxSum([1, -2, 3, 4, -5, -4, 3, 2, 1], [[0, 8], [1, 3], [0, 4], [6, 8]]);

answered Jun 23, 2020 at 14:36

pretzelhammer

15.4k16 gold badges56 silver badges105 bronze badges

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

3 Comments

Quintis Over a year ago

map(([a, b]) => left[b + 1] - left[a]) - interesting use case

Quintis Over a year ago

pretzelhammer , please , can you show detailed description of this function ?

user120242 Over a year ago

precalculate sum(0...n) for n=[0...length], return sum(0...n1) - sum(0..n2) = sum(n1..n2)

Collectives™ on Stack Overflow

How accelerate reduce and forEach method?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related