Ссылка на проблему: https://leetcode.com/problems/maximum-subarray/
Цель задачи - найти максимальную сумму смежных значений в массиве.
Вот пара примеров входов и выходов:
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6. Input: [-2,-11,-13,-2,-14,-9,-5,-15,-3], Output: -2 Explanation: [-2] has the largest sum = -2. Input: [-2,0,-1] Output: 0 Explanation: [0] has the largest sum = 0.
Решение грубой силы
Это наиболее очевидное решение, но, к сожалению, не очень эффективное. Я не буду проводить здесь слишком много времени, но основная идея состоит в том, что вы вычисляете сумму всех возможных смежных подмассивов и играете «королем горы» с помощью переменной maxSum. Я расскажу об этом ниже.
Интуиция:
→ Просканируйте каждую ячейку в массиве.
→ Инициализируйте maxSum и установите для него значение -Infinity.
→ • Установите для currSum значение 0.
→ • Просканируйте, начиная с текущего индекса и до конца массива.
& Rarr; & lt; & lt; & rs; & rsum; Если да, то присвойте currSum параметру maxSum.
→ Вернуть maxSum
Код:
function findMaxSubArrayBruteForce(arr) { let maxSum = -Infinity; let currSum; for (var i = 0; i < len; i++) { currSum = 0; for (var j = i; j < len; j++) { currSum += arr[j]; if (maxSum < currSum) { maxSum = currSum; } } } return maxSum; }
Анализ Big O:
Время: O (n²)
Вложенный цикл for выполняет операцию n².
Пробел: O (1 )
Объем выделенной памяти не увеличивается в зависимости от ввода.
Линейное решение
Ключом к этому решению является понимание роли отрицательных чисел.
Input: [-2,-11,-13,-2,-14,-9,-5,-15,-3], Output: -2 Explanation: [-2] has the largest sum = -2.
В приведенном выше примере все числа отрицательные. Это означает, что сложение двух вместе всегда будет хуже, чем использование меньшего. Однако отрицательные числа могут быть полезны для расчета суммы.
Input: [2,1,-1,4], Output: 6 Explanation: [2,1,-1,4] has the largest sum = 6.
В приведенном выше примере отрицательное число используется как мост между положительными числами с одной стороны и положительными числами с другой. Если мы немного изменим этот пример, то увидим, в какой момент мост бесполезен:
Input: [2,1,-3,4], Output: 4 Explanation: [2,1,-3,4] has the largest sum = 4.
Обнуление суммы первых трех символов. Это означает, что сумма для непрерывного массива по существу начинается заново. Фактически, непрерывный массив может начинаться с 4 (этого третьего индекса), и это даже не имеет значения.
С этим пониманием наша стратегия может начать нашу currSum с нуля, если она упадет ниже нуля.
Интуиция:
→ Инициализировать currSum, равным 0, и maxSum, равным -Infinity.
→ Просканировать каждую ячейку в массиве.
→ • Проверьте, не меньше ли currSum.
→ • Если да, присвойте ему значение 0.
→ • Добавить значение текущего индекса в currSum
→ • Проверить, больше ли currSum, чем maxSum
→ • • Если да, то назначить maxSum для currSum.
→ Вернуть maxSum
Код:
function maxSubarray(nums) { let currSum = -Infinity; let maxSum = -Infinity; for(let i = 0; i < nums.length; i++) { currSum = Math.max(0, currSum); currSum += nums[i]; maxSum = Math.max(maxSum, currSum); } return maxSum; }
Анализ Big O:
Время: O (n)
Простое линейное сканирование массива.
Пробел: O (1)
Нет памяти не масштабируется на основе ввода.