如果从连续段中选取相同的数字,则计算最大总和

Question

如果从连续段中选取相同的数字,则计算最大总和

[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

除了O(n ^ 2)循环,我想不出任何解决方案

Answer 1

O(n)复杂.使用堆栈.虽然数字正在增加推送索引以进行堆叠.如果数字等于或低于数组或数组结束,则从堆栈中弹出相等或更大数字的索引并进行计算.继续.

JavaScript代码:

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]))