[Решение 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