Avoid using nested loops to find the max-sized sub-string of an array?

Question

Added maximum number according to the input length should be returned.

For example, if the length is 2 then the max among arr[0] + arr[1], arr[1] + arr[2], arr[2] + arr[3] should be returned.

Input is array and length.

I solved this in a real job interview but I think there will be a way not to use nested loop.

const add = (arr, len) => {
  let rtnVal = 0

  for (let i = len - 1; i < arr.length; i++) {
    let temp_idx = i;
    let temp_sum = 0;
    for (let j = 0; j < len; j++) {
      temp_sum = (temp_sum || 0) + arr[temp_idx]
      temp_idx -= 1
    }

    if (temp_sum > rtnVal) {
      rtnVal = temp_sum
    }
  }

  return rtnVal
}

console.log(add([1, 2, 3, 4, 5, 6, 7, 8, 9], 4))

I expect the output 30

// enhanced nested loop

const add = (arr, len) => {
  let rtnVal = 0;
  for(let i=len-1;i<arr.length;i++){
    let sum = 0
    for(let j=i;j>=i-len+1;j--){
      sum += arr[j]
    }
    if (sum > rtnVal) rtnVal = sum
  }
  return rtnVal

}
console.log(add([9, 9, 9, 4, 5, 6, 7, 8, 9], 3))

Loop once, but keep head and tail “pointers”. On each move forward, add the head value and subtract the tail value from the running sum. Track max along the way. — randomir
– randomir, Commented May 22, 2019 at 5:11
Same base question, but some detail are different: algorithm - How to solve "fixed size maximum subarray" using divide and conquer approach? - Stack Overflow — user202729
– user202729, Commented Jun 4, 2019 at 15:06

Ouroborus · Accepted Answer · 2019-06-05 08:35:36Z

4

Use a moving window. Add up len numbers starting at the beginning. Then continue through the array adding the next number and subtracting the trailing number.

const add = (arr, len) => {
  return arr.reduce((a,v,i,arr) => {
    a.running += v;
    if(i >= len) {
      a.running -= arr[i-len];
    }
    if(i+1 >= len && a.largest < a.running) {
      a.largest = a.running;
    }
    return a;
  }, {
    largest: Number.NEGATIVE_INFINITY,
    running: 0
  }).largest;
}

console.log(add([1,2,3,4,5,6,7,8,9],4)); // 30
console.log(add([-1,-1,-1,-1],2)); // -2
console.log(add([1],1)); // 1

edited Jun 5, 2019 at 8:35

answered May 22, 2019 at 5:23

Ouroborus

17k8 gold badges42 silver badges65 bronze badges

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

4 Comments

user202729 Over a year ago

The condition a.largest < a.running should only be executed when i >= len-1, otherwise the result would be (wrong) -1 for len > 1 and arr full of -1.

Ouroborus Over a year ago

@user202729 I'm not sure that i >= len-1 is correct but I do see that the constraint needs to, at least, be i >= len to account for negative integers near the beginning of the array. I'm going to assume that arr.length >= len is true.

user202729 Over a year ago

No, this is still wrong because it doesn't take into account the leftmost array. Try a = [1], len = 1.

Ouroborus Over a year ago

@user202729 Ah, okay, I see now.

Priyesh Diukar · Accepted Answer · 2019-05-22 05:57:03Z

1

Assuming its sorted like your example. You can use negative slice to select from end and then reduce the array.

const add = (arr, len) => arr.slice(len > arr.len ? arr.len : -len).reduce((total, num) => total + num)

console.log(add([1, 2, 3, 4, 5, 6, 7, 8, 9], 4))

edited May 22, 2019 at 5:57

answered May 22, 2019 at 5:21

Priyesh Diukar

2,1241 gold badge17 silver badges19 bronze badges

1 Comment

Ryan Kim Over a year ago

I'm sorry but your answer doesn't bring the answer I expect. I think this only works when input array values are sorted. Thanks

Collectives™ on Stack Overflow

Avoid using nested loops to find the max-sized sub-string of an array?

2 Answers 2

4 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related