🔼

Оценка

Временная сложность этого решения - 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

[Решение] Leetcode #153. Find Minimum in Rotated Sorted Array

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

Само условие (что сложность должна быть не более O(log n)) подсказывает нам, что следует использовать подход "разделяй и властвуй".

Берем исходный массив и находим его середину. Теперь нужно выяснить, в какой части массива (левой или правой) нужно продолжить поиск.

Тут может быть две ситуации:

- центральный элемент меньше первого элемента массива
например, [4,5,1,2,3] или [5,1,2,3,4]
тогда либо центральный элемент искомый, либо мы продолжаем поиск в левой части массива

- центральный элемент больше первого элемента массива
например, [1,2,3,4,5] или [3,4,5,1,2]
тогда либо первый элемент искомый, либо мы продолжаем поиск в правой части массива

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

function findMin(nums: number[]): number {
  let start = 0;
  let end = nums.length - 1;
  let min = Infinity;

  while(start <= end) {
    const mid = Math.floor((start + end) / 2);
    if (nums[start] <= nums[mid]) {
      min = Math.min(min, nums[start]);
      start = mid + 1;
    } else {
      min = Math.min(min, nums[mid]);
      end = mid - 1;
    }
  }

  return min;
}

#medium #arrays #divideandconquer

@leetcode_furrycat

[Условие]. Leetcode #33. Search in Rotated Sorted Array

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

Тут мы снова имеем дело с rotated массивами (можно посмотреть в предыдущей задачке подробнее). На этот раз нам нужно искать конкретный элемент в таком "прокрученном" массиве. Нужно вернуть либо индекс искомого элемента, либо -1, если элемента в массиве нет.

Кейс 1
nums = [4,5,6,7,0,1,2], target = 0
ответ: 4

Кейс 2
nums = [4,5,6,7,0,1,2], target = 3
ответ: -1

Необходимо решить задачку за O(log n).

#medium #arrays #divideandconquer

@leetcode_furrycat

[Решение] Leetcode #33. Search in Rotated Sorted Array

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

Решение довольно простое. Как и в предыдущем примере мы берем массив, находим средний элемент и делим массив пополам. Проверив ряд простых условий, определяем, в какой половине продолжать поиск.

Основная сложность здесь - учесть все возможные ситуации.

function search(nums: number[], target: number): number {
    let start = 0 
    let end = nums.length - 1
    
    while(start <= end) {
        const mid = Math.floor((start + end) / 2)

        if (nums[mid] === target) return mid

        if (nums[start] <= nums[mid]) {
            if (target >= nums[start] && target < nums[mid]) {
                end = mid - 1 
            } else {
                start = mid + 1
            }
        } else {
            if (target > nums[mid] && target <= nums[end]) {
                start = mid + 1
            } else {
                end = mid - 1
            }
        }
    }

    return -1
}

#medium #arrays #divideandconquer

@leetcode_furrycat

[Условие]. Leetcode 15. 3Sum

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

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

Кейс 1
nums = [-1,0,1,2,-1,4]
ответ: [ [-1, -1, 2], [-1, 0, 1] ]

Кейс 2
nums = [0,1,1]
ответ: []

Кейс 3
nums = [0,0,0]
ответ: [[0,0,0]]

#medium #arrays #twopointers

@leetcode_furrycat

[Решение] Leetcode #15. 3Sum

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

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

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

function threeSum(nums: number[]): number[][] {
    if (nums.length < 3) return [];

    nums.sort((a, b) => a - b);
    if (nums[0] > 0) return [];

    const triplets = [];

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > 0) break;
        if (nums[i] === nums[i - 1]) continue;

        let j = i + 1;
        let k = nums.length - 1;
        
        while(j < k) {
            const sum = nums[i] + nums[j] + nums[k];
            if (sum === 0) {
                triplets.push([nums[i], nums[j], nums[k]]);
                j++;
                k--;
            } else if (sum < 0) {
                j++;
            } else {
                k--;
            }
        }
    }

    return triplets;
}

#medium #arrays #twopointers

@leetcode_furrycat

[Условие]. Leetcode 11. Container With Most Water

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

У нас есть несколько вертикальных линий, расположенных последовательно через равное расстояние. На вход получаем массив, в котором содержатся их высоты.
Задача - найти максимальную площадь прямоугольника, сторонами которого являются две из этих линий.

Кейс 1
height = [1,8,6,2,5,4,8,3,7] (на картинке)
Ответ: 49 (между линиями с высотой 8 и 7)

#medium #arrays #twopointers

@leetcode_furrycat

[Решение]. Leetcode 11. Container With Most Water

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

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

function getVolume(height: number[], left: number, right: number): number {
    const h1 = height[left]
    const h2 = height[right]
    return Math.min(h1, h2) * (right - left)
}

function maxArea(height: number[]): number {
    let left = 0
    let right = height.length - 1
    let max = 0

    while(left < right) {
        max = Math.max(max, getVolume(height, left, right))

        if (height[left] < height[right]) {
            left++
        } else {
            right--
        }
    }

    return max
}

#medium #arrays #twopointers

@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