dynamic-programming - 如果从连续段中选取相同的数字，则计算最大和

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

[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）循环外，我想不出任何解决方案

最佳答案

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

关于dynamic-programming - 如果从连续段中选取相同的数字，则计算最大和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48614633/