dynamic programming - calcular la suma máxima si se selecciona el mismo número del segmento continuo

dynamic-programming

Question

calcular la suma máxima si se selecciona el mismo número del segmento continuo

[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

No puedo pensar en ninguna solución excepto el bucle O (n ^ 2)

Answer 1

La respuesta de @ גלעד ברקן es correcta y debe ser aceptada. Sin embargo, decidí implementar la solución de pila por interés y ayudar a @xyz a resolverlo.

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;
}

Answer 2

O(n) complejidad. Usa una pila. Mientras que los números están aumentando los índices de empuje para apilar. Si el número es igual o inferior o la matriz finaliza, extraiga los índices de números iguales o mayores de la pila y calcule. Continuar.

Código de 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]))