[Решение 1] Leetcode #238. Product of Array Except Self

Условие задачи

Предположим, что наш входной массив выглядит так: [a,b,c,d].

Попробуем пройти по нему в одну сторону, вычисляя для каждого элемента произведение всех предыдущих членов (префиксное произведение).

для элемента 0
nums[0] = a
предыдущих членов нет

для элемента nums[1] = b
произведение предыдущих членов = a

для элемента nums[2] = c
произведение предыдущих членов = a * b

для элемента nums[3] = d
произведение предыдущих членов = a * b * c

Тут можем вывести простую формулу:

production(i) = production(i - 1) * nums[i - 1]

или словами: для каждого элемента i произведение предыдущих элементов равно:
произведение, вычисленное для i-1,
умножить на элемент i-1.

Получится вот такой промежуточный результат:

[undefined, a, ab, abc]

Теперь пройдем в другую сторону и сделаем то же самое (постфиксное произведение):

[bcd, cd, d, undefined]

Если объединить эти два массива, мы получим решение задачи:

[bcd, a * cd, ab * d, abc]

Мы можем использовать подход с двумя указателями, чтобы одновременно идти по массиву с двух сторон. Тут важно хранить оба массива отдельно, чтобы элементы не дублировались, а в результат записывать уже результат их объединения.

Так как мы идем по массиву с обоих сторон одновременно, в одном цикле, временная сложность получается всего O(n).
Но и памяти мы тратим прилично - для хранения двух промежуточных массивов.

#medium #arrays #prefixsum

@leetcode_furrycat

[Решение 2] Leetcode #238. Product of Array Except Self

Условие задачи

А вот и более изящное решение, основанное на том же подходе префиксных и постфиксных произведений (см. предыдущий пост).

Мы не будем хранить массивы с вычисленными значениями, мы будем просто накапливать значение префиксного и постфиксного произведения.

Начнем с нуля и пойдем по массиву, увеличивая одновременно префиксное произведение для элемента i и постфиксное произведение для элемента nums.length - i - 1 и обновляя соответствующие индексы в результирующем массиве.

Исходные данные:

nums = [a,b,c,d]
result = [1,1,1,1] // заполняем единицами
len = nums.length
pre = 1 // накопл. префиксное произв. для i-го элемента с начала массива
post = 1 // накопл. постфиксное произв. для i-го элемента с конца массива

На каждом шаге делаем следующее:

// обновляем результат для элемента i с начала массива
result[i] = result[i] * pre 
// увеличиваем pre для следующего элемента 
pre = pre * nums[i]
// обновляем результат для элемента i с конца массива 
result[len - i - 1] = result[len - i - 1] * post 
// увеличиваем post для следующего элемента 
post = post * nums[len - i - 1]

Промежуточные результаты по шагам:

i = 0 
result = [1, 1, 1, 1]
pre = a 
post = d 

i = 1
result = [1, a, d, 1]
pre = ab 
post = cd 

i = 2 
result = [1, acd, abd, 1]
pre = abc 
post = bcd 

i = 3 
result = [bcd, acd, abd, abc]
pre = abcd 
post = abcd

#medium #arrays #prefixsum

@leetcode_furrycat

[Условие] Leetcode #53. Maximum Subarray

Ссылка на задачу на Leetcode
Решение

Получаем на вход массив целых чисел nums. Необходимо найти подмассив с самой большой суммой элементов. На выходе должна быть сумма элементов подмассива.

Подмассив - это непрерывная и непустая последовательность элементов. Сам массив тоже является своим подмассивом.

Кейс 1
nums = [-2,1,-3,4,-1,2,1,-5,4]
Ответ: 6
Объяснение: подмассив с самой большой суммой [4, -1, 2, 1]

Кейс 2
nums = [1]
Ответ: 1

Кейс 3
nums = [5,4,-1,7,8]
Ответ: 23
Объяснение: подмассив с самой большой суммой [5,4,-1,7,8]

Примечание: если получится найти решение со сложностью O(n), постарайтесь найти более "изящное" решение с использованием подхода "разделяй и властвуй".

#medium #arrays #dp #recursion #divideandconquer #prefixsum

@leetcode_furrycat

[Решение 1. Рекурсия] Leetcode #53. Maximum Subarray

Условие задачи

Эту задачу можно решить несколькими способами (помимо грубой силы). Мы начнем с рекурсии.

🔹Логика такая:

У нас есть массив чисел [a,b,c,d] с первым элементом a:

[a, ...rest]

Для этого элемента есть всего два возможных варианта:
1. он либо входит в искомый максимальный подмассив
2. либо не входит

Каждый из этих вариантов мы обработаем, а потом просто сравним два полученных результата и выберем максимальный.

В любом случае мы этот элемент временно откладываем и переходим к массиву массиву rest. Его можно представить в таком же виде:

[b, ...rest2]

Таким образом будем рекурсивно погружаться, пока массив не кончится.

🟢 Вариант 1 (элемент входит в искомый подмассив)

Назовем это firstElementMustPick = true.

Если мы предполагаем, что a входит в искомый подмассив, то на следующем витке рекурсии у нас появляется некоторая определенность.

Элемент b совершенно точно входит в искомый максимальный массив, так как мы не можем разрывать подмассив. Поэтому для него нужно будет обработать только один вариант и не нужно ничего сравнивать.

Важно не забыть, что у нас есть еще элемент a, который тоже входит в этот подмассив. Его нужно будет прибавить к полученному результату.

🟢 Вариант 2 (элемент не входит в искомый подмассив)

firstElementMustPick = false.

Просто повторяем те же самые предположения:

1 - b входит в искомый подмассив
2 - или b не входит в искомый подмассив

Сравниваем 1 и 2, чтобы найти максимум.

🟢 Функция

Выглядеть все это будет примерно так:

function getMaxSubarraySum(nums, startIndex = 0, firstElementMustPick = false) {
    const currentElement = nums[startIndex]
    const sumWithFirstElement = currentElement + getMaxSubarraySum(nums, startIndex + 1, true);

    if (firstElementMustPick) {
        return sumWithCurrentElement;
    }

    const sumWithoutFirstElement = getMaxSubarraySum(nums, startIndex + 1, false);

    return Math.max(sumWithCurrentElement, sumWithoutCurrentElement)
}

🟢 Крайний случай

Рано или поздно мы доберемся до крайнего случая, когда наш массив закончится (когда startIndex достигает длины массива `nums`).

Например, массив изначально состоял из одного элемента:

const nums = [f]

Опять рассматриваем два варианта для элемента f:

1 - f входит в подмассив
2 - f не входит в подмассив

const sumWithFirstElement = f + getMaxSubarraySum(nums, 1, true);
const sumWithoutFirstElement = getMaxSubarraySum(nums, 1, false);
return Math.max(sumWithCurrentElement, sumWithoutCurrentElement);

Что должна вернуть функция getMaxSubarraySum в первом и втором случае?

Тут становится очевидно, что в крайнем случае функция должна возвращать разные значения в зависимости от параметра firstElementMustPick. В первом случае - 0, чтобы не повлиять на общую сумму. Во втором случае - очень маленькое значение, чтобы всегда проигрывать в сравнении.

if (startIndex >= nums.length) {
    if (firstElementMustPick) return 0;
    return -Infinity;
}

🟢 Полный код

function getMaxSubarraySumRecursive(nums, startIndex, firstElementMustPick) {
 if (startIndex >= nums.length) {
  if (firstElementMustPick) return 0;
  return -Infinity;
 }

    const currentElement = nums[startIndex];

    const sumWithFirstElement = currentElement + getMaxSubarraySumRecursive(nums, startIndex + 1, true);

    if (firstElementMustPick) {
        return Math.max(sumWithCurrentElement, 0);
    }

    const sumWithoutFirstElement = getMaxSubarraySumRecursive(nums, startIndex + 1, false); 

    return Math.max(sumWithFirstElement, sumWithoutFirstElement)
}

function maxSubArray(nums: number[]): number {
 return getMaxSubarraySumRecursive(nums, 0, false);
}

#medium #arrays #recursion

@leetcode_furrycat

🔼

Оценка

Временная сложность этого решения - O(n^2). Для каждого элемента мы запускаем две ветки выполнения, каждая из которых проходит по всему массиву. Это очень много, и на Leetcode это решение проваливается на очень большом массиве.

Но это решение хорошо подходит для оптимизации с помощью методов динамического программирования.

#medium #arrays #recursion

@leetcode_furrycat

[Решение 2. ДП, мемоизация] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Если посмотреть на рекурсивное решение задачи https://yangx.top/leetcode_furrycat/29 повнимательнее, то можно заметить, что у нас много повторяющихся вычислений: сначала мы для нулевого элемента массива считаем все последующие комбинации (от 1 до конца, от 2 до конца, от 3 до конца). Потом для первого считаем практически то же самое (от 2 до конца, от 3 до конца и т.д.)

Когда такое происходит, самое время использовать мемоизацию. Код останется точно таким же, просто прежде чем делать вычисление мы будем проверять, не сделано ли оно ранее. Хеш будет выглядеть примерно так:

const nums = [5,4,-1,7,8]
const dp = {
    0: [23,18,15,15,8],
    1: [null, 18,14,15,8]
}

Ключи 0 и 1 - это значения параметра firstElementMustPick, а массивы чисел - это максимальные суммы для каждого элемента исходного массива. Рассчитываем их один раз, а потом просто переиспользуем.

#medium #arrays #dp

@leetcode_furrycat

[Решение 3.1. ДП, табуляция] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Раз уж мы заговорили о динамическом программировании, можно попробовать и второй подход - табуляцию (решать задачи, начиная с самой простой).

Возьмем сначала самый маленький подмассив (состоящий из одного элемента) и посчитаем сумму для него - сохраним это значение.

Затем увеличим этот массив на один элемент. Новый элемент может:
1) входить в искомый подмассив вместе с предыдущим
2) входить в искомый подмассив самым первым (открывать его)
3) не входить в искомый подмассив

В dp[1][i] мы сохраним максимальный вариант из 1) и 2).
А в dp[0][i] - максимальный вариант из ранее сохраненного (`dp[0][i-1]`) и только что посчитанного (`dp[1][i]`).

В dp[1] мы будем хранить значения с учетом того, что элемент входит в подмассив, а в dp[0] - без учета, то есть просто максимально возможное значение.

Таким образом, в кеше в элементе с индексом i у нас будет находиться максимальная сумма для соответствующего элемента массива nums (точнее для подмассива [0, i]).

Пошаговый разбор:

const nums = [-2,1,-3,4,-1,2,1,-5,4]
const dp = {
    0: [-2],
    1: [-2]
}

i = 1
если i-й элемент входит в подмассив
- то он либо следует за предыдущим элементом (dp[1][0] + nums[1] = -2 + 1 = 1)
- либо начинает этот массив сам (nums[1] = 1)
находим максимум и добавляем в кеш

если i-й элемент не входит в подмассив
находим максимум между предыдущим значением в этом массиве (максимальная сумма для предыдущего элемента) dp[0][i - 1] = -2
и только что посчитанной максимальной суммой для текущего dp[1][i] = 1

dp = {
    0: [-2, 1],
    1: [-2, 1]
}

i = 2
dp[1][2] = Math.max(dp[1][1] + nums[2], nums[2]) = Math.max(1 + -3, -3) = -2
dp[0][2] = Math.max(dp[0][1], dp[1][2]) = Math.max(1, -3) = 1

Ответом всегда будет последнее значение в dp[0], так как там хранится максимально возможная сумма подмассива для последнего индекса.

#medium #arrays #dp

@leetcode_furrycat

[Решение 3.2. ДП, табуляция] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Предыдущее решение с использованием метода табуляции можно еще больше упростить. Там мы сохраняли каждое промежуточное значение - даже два для каждого элемента (в вхождением в подмассив и без). Но в принципе мы можем просто сразу выбирать самое большое из возможных для данного индекса значений:

- сумма, накопленная для предыдущего элемента, плюс текущий элемент
- или только текущий элемент (если предыдущая сумма отрицательна)

Чтобы найти ответ, нужно просмотреть весь полученный массив и взять самое большое число.

const dp = [...nums]

for (let i = 1; i < nums.length; i++) {
    dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
}

return Math.max.apply(null, dp);

#medium #arrays #dp

@leetcode_furrycat

🔼 Временная сложность алгоритмов, использующих приемы динамического программирования, - O(n), так как по массиву мы проходим только один раз, и используем при этом ранее вычисленные значения.


#medium #arrays #dp

@leetcode_furrycat

[Решение 3.3. ДП, алгоритм Кадане] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Мы можем пойти еще дальше и отказаться от массива dp. На самом деле на каждом шаге нам нужно лишь предыдущее значение, значит, и хранить можно только его.

На самом деле мы будем хранить два значения - локальную сумму (локальный максимум) и глобальный максимум. Локальная сумма непрерывна, мы всегда сравниваем предыдущее накопленное значение и его сумму с текущим элементом. В глобальный максимум будем заносить только самые большим величины - он заменит нам финальный поиск самого большого элемента в массиве dp:

function kadane(nums) {
    let currentMax = 0;
    let maxTillNow = - Infinity;

    for (let i = 0; i < nums.length; i++) {
        const el = nums[i];
        currentMax = Math.max(el, currentMax + el);
        maxTillNow = Math.max(maxTillNow, currentMax)
    }

    return maxTillNow;
}

Временная сложность у этого алгоритма тоже равна O(n), зато пространственная всего O(1).

#medium #arrays #dp

@leetcode_furrycat

[Решение 4.1. Разделяй и властвуй] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

Стратегия "Разделяй и властвуй" предполагает деление исходного массива на несколько частей. Мы будем делить на три (левую L, правую R и центральный элемент `mid`). Тогда наш искомый подмассив с максимальной суммой может лежать:

- полностью в левой части L (от 0 до `mid-1`)
- полностью в правой части R (от mid+1 до `n.length-1`)
- либо включает в себя обязательно центральный элемент mid и возможно части L и R, которые находятся рядом с mid

Для L и R мы запустим рекурсивное вычисление. Для третьего случая посчитаем максимальную сумму. Потом сравним три значения и вернем максимальное.

function getMaxSubArraySum(nums, left, right) {
    left = left ?? 0; // начало анализируемого подмассива
    right = right ?? nums.length - 1; // конец анализируемого подмассива

    if (left > right) return -Infinity;

    const mid = Math.floor((left + right) / 2); // середина анализируемого подмассива

    // рекурсивно считаем для левой и правой частей
    const maxLeftSubArraySum = getMaxSubArraySum(nums, left, mid - 1);
    const maxRightSubArraySum = getMaxSubArraySum(nums, mid + 1, right);

    // находим подмассив с максимальной суммой, 
    // который содержит элемент mid 

    let leftMaxSum = 0;
    let rightMaxSum = 0;

    // для L идем с конца, так как подмассив должен быть рядом с mid
    // считаем непрерывную сумму элементов и отбираем максимальную

    for (let i = mid - 1, currentLeftSum = 0; i >= left; i--) {
        currentLeftSum += nums[i];
        leftMaxSum = Math.max(leftMaxSum, currentLeftSum);
    }

    // то же для R 

    for (let i = mid + 1, currentRightSum = 0; i <= right; i++) {
        currentRightSum += nums[i];
        rightMaxSum = Math.max(rightMaxSum, currentRightSum);
    }

    const maxCenterSubArraySum = leftMaxSum + nums[mid] + rightMaxSum;

    return Math.max(maxLeftSubArraySum, maxRightSubArraySum, maxCenterSubArraySum)
}

Временная сложность этого решения - ожидаемо O (n * log n). Мы делаем log n разделений и для каждого считаем maxCenterSubArraySum, что требует перебора массива (n).

Пространственная сложность: O (log n) - так как у нас рекурсия.

#medium #arrays #divideandconquer #recursion

@leetcode_furrycat

[Решение 4.2. Оптимизация Разделяй и властвуй] Leetcode #53. Maximum Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/28

И наконец, мы можем еще сократить время выполнения алгоритма, заранее посчитав префиксные и суффиксные суммы.

const prefixes = [...nums]
const suffixes = [...nums] 

for (i = 1; i < nums.length; i++) {
  const previousSum = prefixes[i - 1];
  prefixes[i] += Math.max(0, previousSum);
}

for (i = nums.length - 2; i >= 0; i--) {
  const previousSum = suffixes[i + 1];
  suffixes[i] += Math.max(0, previousSum;
}

Теперь рассчитать maxCenterSubArraySum намного проще:

const maxCenterSubArraySum = prefixes[mid] + suffixes[mid+1]

Временная сложность: O(n)
Пространственная сложность: O(n)

#medium #arrays #divideandconquer #prefixsum

@leetcode_furrycat

[Решение] Leetcode #53. Maximum Subarray

Условие задачи

Итого у нас получилось больше 5 способов решить одну и ту же задачку.

0 - Brute force
1 - Простая рекурсия
2 - Рекурсия с мемоизацией вычислений
3 - Табуляция, оптимизированная табуляция
4 - Алгоритм Кадане
5 - Разделяй и властвуй + оптимизация с предварительным расчетом

#medium #arrays #dp #divideandconquer #recursion #prefixsum

@leetcode_furrycat

[Условие] Leetcode #152. Maximum Product Subarray

Ссылка на задачу на Leetcode
Решение

Условие похоже на предыдущую задачу:

Получаем на вход массив целых чисел nums. Необходимо найти подмассив (непрерывный и непустой) с самым большим произведением элементов.

Кейс 1
nums = [2,3,-2,4]
Ответ: 6
Объяснение: [2,3]

Кейс 2
nums = [-2,0,-1]
Ответ: 0
Объяснение: 2 получиться не может, так как [-2,-1] это не подмассив, все остальные варианты дают 0 или отрицательное число

#medium #arrays #dp #prefixsum

@leetcode_furrycat

[Решение] Leetcode #152. Maximum Product Subarray

Условие задачи: https://yangx.top/leetcode_furrycat/39

Задачка с поиском подмассива с максимальным произведением похожа на задачу с поиском подмассива с максимальной суммой, поэтому и решать мы ее будем похожим образом: с использованием алгоритма Кадане.

Для задачи с наибольшей суммой его суть заключалась в том, что мы проходили по массиву слева направо и вычисляем наибольшую возможную сумму для ТЕКУЩЕГО элемента (от начала массива до текущего элемента). А затем просто брали максимальное из полученных значений.

Но с произведением все немного по-другому. Здесь у нас есть нули, которые любой подмассив сведут к нулю, а также отрицательные числа, которые по одиночке радикальном уменьшают общее произведение, но парами очень даже увеличивают. То есть здесь мы не можем сказать, что максимально возможное произведение для 2-го элемента - это именно то, что нам нужно, чтобы получить максимальное произведение для 3-го элемента.

Пример:

const nums = [-2, 3, -4]

для n=1: maxTillNow = -2
для n=2: maxTillNow = Math.max(3, -6) = 3
для n=3: maxTillNow = Math.max(3, -12) = 3

Очевидно, что этот алгоритм неправильный, и чтобы получить максимум для третьего элемента, нам следует взять -6 на предыдущем шаге.

В целом очевидно, что для массива состоящего только из положительных чисел максимальным подмассивом является сам этот массив (все элементы, умноженные друг на друга). Поэтому мы будем вычислять произведение непрерывно. То есть для каждого элемента мы найдем произведение ВСЕХ элементов до него, включая сам активный элемент.

Если в какой-то момент накапливаемое произведение стало равно 0, значит, нам попался элемент 0. В этом случае просто сбросим его до исходной единицы и продолжим считать уже после этого элемента.

А чтобы избежать разнообразных эксцессов с отрицательными числами, пройдем по массиву два раза - слева направо и справа налево:

1 - Если в массиве четное количество отрицательных чисел, то очевидно, что при обратном проходе ничего не изменится.
2 - Если же в массиве нечетное количество отрицательных чисел, то с помощью второго прохода мы сможем получить все комбинации подмассивов (слева и справа от отрицательного числа) и выбрать максимальную.

function maxProduct(nums) {
    let currentProduction = 1;
    let maxTillNow = -Infinity;

    for (let i = 0; i < nums.length; i++) {  
        const el = nums[i];
        currentProduction *= el;
        maxTillNow = Math.max(maxTillNow, currentProduction);
        if (currentProduction === 0) {
            currentProduction = 1;
        }
    }

    currentProduction = 1;

    for (let i = nums.length - 1; i >= 0; i--) {
        const el = nums[i];
        currentProduction *= el;
        maxTillNow = Math.max(maxTillNow, currentProduction);
        if (currentProduction === 0) {
            currentProduction = 1;
        }    
    }

    return maxTillNow;
}

Временная сложность: O(N) - мы делаем два прохода по массиву, но коэффициент отбрасывается

#medium #arrays #dp #prefixsum

@leetcode_furrycat

[Условие] Leetcode #153. Find Minimum in Rotated Sorted Array

Ссылка на задачу на Leetcode
Решение

На вход мы получаем отсортированный в порядке возрастания массив уникальных целых чисел - nums и должны найти в нем минимальный элемент.

Слишком просто, да?) Да, загвоздка в том, что массив у нас rotated ("прокручен" что ли) несколько раз.

Например, если у нас есть массив [0,1,2,3,4] и мы его один раз "прокрутим", получится [4,0,1,2,3]. Если еще один раз прокрутим, будет [3,4,0,1,2].

Так вот наш массив прокручен от 1 до n раз. И мы должны найти в нем минимальный элемент. И сделать это нужно алгоритмом с временной сложностью не более, чем O(log n).

Кейс 1
nums = [3,4,5,1,2]
ответ: 1
объяснение: оригинальный отсортированный массив [1,2,3,4,5] прокручен 3 раза

#medium #arrays #divideandconquer

@leetcode_furrycat