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