[Условие] 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

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

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

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

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

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

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

@leetcode_furrycat

Blind 75. Arrays

Небольшое ретро по задачкам из раздела Массивы:

1 - Two sum (easy)
11 - Container With Most Water (medium)
15 - 3Sum (medium)
33 - Search in Rotated Sorted Array (medium)
53 - Maximum Subarray (medium)
121 - Best Time to Buy and Sell Stock (easy)
152 - Maximum Product Subarray (medium)
153 - Find Minimum in Rotated Sorted Array (medium)
217 - Contains Duplicate (ease)
238 - Product of Array Except Self (medium)

Какие подходы к решению использовались:

👉 Два указателя (#twopointers)

Используется, когда "второй" элемент всегда идет после "текущего". Часто используется для отбора последовательно идущих элементов, которые в комбинации соответствуют определенному условию.

- два/три элемента, составляющие определенную сумму (Two sum, 3Sum)
- две линии, составляющие прямоугольник наибольшей площади (Container With Most Water)
- две даты, между которыми акция росла больше всего (Best Time to Buy and Sell Stock)

👉 Хеш-таблица (#hashtable)

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

- Быстро найти второе слагаемое для известной суммы и первого слагаемого (Two sum)
- Найти дубликаты ( Contains Duplicate)

👉 Разделяй и властвуй (#divideandconquer)

Используется с отсортированными массивами, когда есть возможность определить, в какой части массива находится нужное значение. Часто используется для поиска (бинарный поиск) элемента (Search in Rotated Sorted Array, Find Minimum in Rotated Sorted Array). Но может использоваться и в более сложном виде, например, для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Рекурсия (#recursion)

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

Например, мы использовали рекурсию для поиска подмассива с максимальной суммой (Maximum Subarray).

👉 Динамическое программирование (#dp)

У динамического программирования есть несколько разновидностей: мемоизация и табуляция. Сюда же можно включить вычисление префиксных сумм (#prefixsum). Подвидом ДП является алгоритм Кадане.
Суть метода в том, что мы используем результаты предыдущих вычислений.
Динамическое программирование часто используется в задачах с массивами для нахождения подмассива с заданными свойствами, например, с максимальной суммой (Maximum Subarray, Maximum Product Subarray)
Также с его помощью (префиксные суммы) мы вычисляли произведение всех элементов массива кроме текущего (Product of Array Except Self).

👉 Set

При работе с массивами может быть полезна структура данных Set, которая позволяет быстро удалить дубликаты из массива (Contains Duplicate), а также обеспечивает быстрый доступ к элементам массива по их значению.

#arrays #ретро

@leetcode_furrycat