Сборка от 17 марта 2017 г

Подмассив наибольшей суммы

важность: 2

На входе массив чисел, например: arr = [1, ‐2, 3, 4, ‐9, 6] .

Задача – найти непрерывный подмассив arr , сумма элементов которого максимальна. Ваша функция должна возвращать только эту сумму.

Например:

getMaxSubSum([‐1, getMaxSubSum([
, ‐9]) = 5 (сумма выделенных)
, ‐9]) = 6

getMaxSubSum([‐1, 2, 3, ‐9, 11]) = 11
getMaxSubSum([‐2, ‐1, 1, 2]) = 3

getMaxSubSum([ getMaxSubSum([
, ‐9, 2, ‐3, 5]) = 100
]) = 6 (неотрицательные ‐ берем всех)

Если все элементы отрицательные, то не берём ни одного элемента и считаем сумму равной нулю:

getMaxSubSum([‐1, ‐2, ‐3]) = 0

Постарайтесь придумать решение, которое работает за O(n²), а лучше за O(n) операций. Открыть песочницу с тестами для задачи. ^

К решению

Массивы: методы

В этой главе мы рассмотрим встроенные методы массивов JavaScript.

Метод split

Ситуация из реальной жизни. Мы пишем сервис отсылки сообщений и посетитель вводит имена тех, кому его отправить: Маша, Петя, Марина, Василий. Но нам‑то гораздо удобнее работать с массивом имен, чем с одной строкой.

К счастью, есть метод split(s) , который позволяет превратить строку в массив, разбив ее по разделителю s . В примере ниже таким разделителем является строка из запятой и пробела.

var names = 'Маша, Петя, Марина, Василий'; var arr = names.split(', ');

for (var i = 0; i < arr.length; i++) { alert( 'Вам сообщение ' + arr[i] );
}