Ссылка на проблему: 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)
Нет памяти не масштабируется на основе ввода.