Найти max сумму элементов пирамиды

266
30 января 2017, 19:47

Есть такая пирамида массивов:

[
  [3],
  [7, 4],
  [2, 4, 6],
  [8, 5, 9, 3] 
]

Нужно найти максимальную сумму ее элементов сверху вниз. Пример:

 /3/
 \7\ 4 
2 \4\ 6 
8 5 \9\ 3

Пока не пойму даже, как реализовать. Пока получается сделать сумму столбцов:

function longestSlideDown(pyramid) { 
  var result = []; 
  for (var i = 0; i < pyramid.length; i++) { 
    var subarr = pyramid[i]; 
    for (var j = 0; j < subarr.length; j++) { 
      if (result[j] == undefined) 
        result[j] = 0; 
      result[j] += subarr[j]; 
    } 
  } 
  return result; 
} 
console.log(longestSlideDown([ 
  [3], 
  [7, 4], 
  [2, 4, 6], 
  [8, 5, 9, 3] 
]));

Answer 1

Нужно прибавлять к результату максимальный результат.

Массив 1: Макс. = 3  
Массив 2: Макс. = 7  
Массив 3: Макс. = 6  
Массив 4: Макс. = 9  

Вот рабочий пример:

function longestSlideDown(pyramid) { 
  var result = 0; 
  for (var i = 0; i < pyramid.length; i++) { 
    var subarr = pyramid[i]; 
    var max = 0; 
    for (var j = 0; j < subarr.length; j++) { 
      if(max < subarr[j]){ 
        max = subarr[j]; 
      }; 
    }; 
    result = result + max; 
  }; 
  return result; 
}; 
 
console.log(longestSlideDown([ 
  [3], 
  [7, 4], 
  [2, 4, 6], 
  [8, 5, 9, 3] 
]));

Вот рабочий пример по условию задачи автора вопроса:

function longestSlideDown(pyramid) { 
  var result = 0, 
      maxElem = null; // Задаём максимальное значение в массиме 
  for (var i = 0; i < pyramid.length; i++) { 
    var subarr = pyramid[i]; 
    var max = 0; // Максимальное число 
    if(maxElem == null){  
      // Если индекса максимального значения нет, то считаем по обычному принципе 
      var maxVal = pyramid[i].length, 
          minVal = 0 
    }else{ 
      // Если значение максимального есть, то ищем элементы с отклонением в один индекс от прошлого максимального 
      var maxVal = maxElem + 1, 
          minVal = maxElem - 1 
    }; 
    for (var j = minVal; j <= maxVal; j++) { 
      if(max < subarr[j]){ 
        maxElem = j; 
        max = subarr[j]; 
      }; 
    }; 
    result = result + max; 
  }; 
  return result; 
}; 
 
console.log(longestSlideDown([ 
  [3], 
  [7, 4], 
  [2, 4, 6], 
  [8, 5, 9, 3] 
]));

Answer 2

Использую особенность reduce и преобразования массива с одним элементом. Если массив с одним элементом преобразовать, то становится строкой. В итоге получается, что в первую итерацию в last передается строка, которую я преобразую в число и складываю со след. значением из след. по списку массива.

const pyramid = [ 
  [3], 
  [7, 4], 
  [2, 4, 6], 
  [8, 5, 9, 3]  
]; 
 
const a = pyramid.reduce((last, cur, i) => { 
	return parseInt(last) + cur[i - 1] 
}); 
 
console.log(a);

Answer 3

let arr = [ 
  [3], 
  [7, 4], 
  [2, 4, 6], 
  [8, 5, 9, 3]  
]; 
 
console.info(arr.reduce((a, _) => a += Math.max(..._), 0));

READ ALSO
Не работает setInterval

Не работает setInterval

Вот в этом коде не работает setInterval()Функция вызывается сама по себе, но setInterval не работает:

349
Не могу взять местоположение

Не могу взять местоположение

Всем приветЕсть карта и на ней Геокардинация

313
resize и разрешение браузера

resize и разрешение браузера

Не могу понять в чем проблема с работой кодаВсе работает отлично, пока я не сменю на iPad (в принципе любой планшет) разрешение, то есть не покручу...

332
chromdriver - no such session error

chromdriver - no such session error

Пытаюсь запустить тесты с использованием:

328