algorithm
Алгоритм максимального субаруса

Алгоритм максимальной субары

Проблема с максимальным субаравием - это метод поиска смежного подмассива в одномерном массиве чисел с наибольшей суммой.

Первоначально проблема была предложена Ульфом Гренандером Университета Брауна в 1977 году как упрощенная модель для оценки максимального правдоподобия моделей в оцифрованных изображениях.

Мы можем решить эту проблему, рассмотрим список различных целых чисел. Нам может быть интересно, в какой сумме будет располагаться полностью смежное подмножество. Например, если у нас есть массив [0, 1, 2, -2, 3, 2] , максимальный подмассив равен [3, 2] с суммой 5 .

Подход Brute-Force для решения:

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

Псевдокод для подхода Brute-Force:

MaxSubarray(array)
  maximum = 0
  for i in input
    current = 0
    for j in input
       current += array[j]
       if current > maximum
         maximum = current
  return maximum

Сложность времени для метода Brute-Force равна O(n^2) . Итак, давайте двигаться, чтобы разделить и победить подход.

Разделить и покорить подход к решению:

Найдите сумму подмассивов с левой стороны, подмассивы справа. Затем просмотрите все те, которые пересекают центральный деление и, наконец, вернут максимальную сумму. Поскольку это алгоритм разделения и покорения, нам нужно иметь две разные функции.

Сначала - шаг разделения,

maxSubarray(array)
  if start = end
    return array[start]
  else
    middle = (start + end) / 2
    return max(maxSubarray(array(From start to middle)), maxSubarray(array(From middle + 1 to end)), maxCrossover(array))

Во второй части отделите другую часть, созданную в первой части.

maxCrossover(array)
  currentLeftSum = 0
      leftSum = 0
  currentRightSum = 0
      rightSum = 0
  for i in array
    currentLeftSum += array[i]
    if currentLeftSum > leftSum
      leftSum = currentLeftSum
  for i in array
    currentRightSum += array[i]
    if currentRightSum > rightSum
      rightSum = currentRightSum
  return leftSum + rightSum

Сложность времени для метода Divide и Conquer - O(nlogn) . Итак, перейдем к подходу к динамическому программированию.

Подход к динамическому программированию:

Это решение также известно как алгоритм Кадана. Это линейный алгоритм времени. Это решение дано Джозефом Б. Кадане в конце 70-х годов.

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

Псевдокод алгоритма Кадане:

MaxSubArray(array)
  max = 0
  currentMax = 0
  for i in array
    currentMax += array[i]
    if currentMax < 0
      currentMax = 0
    if max < currentMax
      max = currentMax
  return max

Сложность времени для алгоритма Кадане - O(n) .

Реализация C #

public class MaximumSubarray
{
    private static int Max(int a, int b)
    {
        return a > b ? a : b;
    }

    static int MaxSubArray(int[] input, int n)
    {
        int max = input[0];
        int currentMax = input[0];
        for (int i = 1; i < n; i++)
        {
            currentMax = Max(input[i], currentMax + input[i]);
            max = Max(max, currentMax);
        }
        return max;
    }

    public static int Main(int[] input)
    {
        int n = input.Length;
        return MaxSubArray(input, n);
    }
}