вычислить максимальную сумму, если тот же номер выбран из непрерывного сегмента

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

Ответ 1

O(n). Используйте стек. Пока числа увеличивают индексы push для стека. Если число равно или меньше или конец массива, введите индексы равных или больших чисел из стека и вычислите. Продолжить.

Код 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]))

Ответ 2

@גלעד ברקן ответ правильный и должен быть принят. Однако я решил реализовать решение стека ради интереса и помочь @xyz разобраться.

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