calculate maximum sum if same number is picked from continuous segment

Question

calculate maximum sum if same number is picked from continuous segment

[1,2,3,4] => answer 6
if 1 is picked from continuous segment [1,1,1,1] then sum is 4 
if 2 is picked from continuous segment [2,3,4] then sum is 6 , 

[6,0,6,5,5,2] => answer 15, continuous segment [6,5,5] , 
5 can be picked from 3 elements.
[1,100,1,1] => answer 100, we can't pick 1 as 1+1+1+1 = 4 <100

I can't think any solution except O(n^2) loop

Answer 1

O(n) complexity. Use a stack. While numbers are increasing push indexes to stack. If the number is equal or lower or the array ends, pop the indexes of equal or larger numbers from the stack and calculate. Continue.

JavaScript code:

function f(arr){
  let stack = [0];
  let best = arr[0];
  
  function collapse(i, val){
    console.log(`Collapsing... i: ${i}; value: ${val}`);
    
    while (stack.length && arr[ stack[stack.length - 1] ] >= val){
      let current_index = stack.pop();
      let left_index = stack.length ? stack[stack.length - 1] : -1;
      console.log(`i: ${i}; popped: ${current_index}; value: ${arr[current_index]}; potential: ${i - left_index - 1} * ${arr[current_index]}`)
      best = Math.max(best, (i - left_index - 1) * arr[current_index]);
    }
  }
  
  console.log('Starting... stack: ' + JSON.stringify(stack));
  
  for (let i=1; i<arr.length; i++){
    if (!stack.length || arr[ stack[stack.length - 1] ] < arr[i]){
      stack.push(i);
      console.log(`Pushing ${i}; stack: ${JSON.stringify(stack)}`);
    
    } else {
      collapse(i, arr[i]);
      stack.push(i);
      console.log(`Pushing ${i}; stack: ${JSON.stringify(stack)}`);
    }
  }
  
  if (stack.length)
    collapse(stack[stack.length - 1] + 1, -Infinity);
  
  return best;
}

//console.log(f([5,5,4]))
//console.log(f([1,2,3,4]))
console.log(f([6,0,6,5,5,2]))

Answer 2

@גלעד ברקן's answer is right and should be accepted. However I decided to implement the stack solution for the sake of interest and to help @xyz sort it out.

let a = [5,5,4,4,6];

console.log(`Answer: ${traverse(a)}`);

function traverse(a) {
    let i, max = 0, stack = [0];
    for (i = 1; i < a.length; i++) {
        if (a[i] >= a[stack[stack.length - 1]]) {
            stack.push(i);
        } else {
            pop(i);
            stack.push(i);
        }
    }
    if (stack.length) pop(i, true);
    function pop(index, end) {
        while (stack.length && (a[stack[stack.length - 1]] >= a[index] || end)) {
            let p = stack.pop();
            let range = stack.length ? index - stack[stack.length - 1] - 1 : index;
            max = Math.max(max, range * a[p]);
        }
    }
    return max;
}