Разделяй и властвуй Проблема максимального подмассива

Подход «разделяй и властвуй» (O(nlogn))

Что такое проблема с максимальным подмассивом?

Постановка задачи проста. Обычно у вас есть массив, заполненный целыми числами (положительные и отрицательные числа), и вам необходимо предоставить самый большой непрерывный (по порядку) подмассив, который существует в этом массиве.

Подмассив и подход

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

Подмассив — это массив, который может быть частью исходного массива или самим массивом целиком.

Например, этот массив [1, 2, 3] может иметь следующие подмассивы: [1], [2], [3], [1,2], [1,3], [2,3] или [1 ,2,3].

Эту проблему можно решить различными способами, наиболее распространенным способом является использование алгоритма Кадане, который приводит к временной сложности O (n). Однако мы не будем обсуждать этот метод. Я думаю, что метод «разделяй и властвуй» дает уникальную перспективу, по крайней мере, для меня, и я поделюсь своими мыслями о нем и о том, как он работает.

Давайте используем этот массив ниже для всей статьи.

Что такое метод «разделяй и властвуй»?

Разделяй и властвуй – это метод решения проблем, состоящий из трех частей: Разделяй, Властвуй и Объединяй.

На шаге «Разделить» вы берете большую проблему и пытаетесь равномерно разделить ее на подзадачи.

Затем на этапе «Завоевание» вы берете эти более мелкие подзадачи и решаете их.

Наконец, вы берете результаты из небольших подзадач и объединяете их обратно в исходную часть, чтобы решить большую проблему.

Вы продолжаете делать эти шаги, пока, наконец, не решите исходную проблему.

Назад к проблеме

Теперь мысленно возвращаемся к проблеме. Он просит нас предоставить самый большой непрерывный подмассив. Что это значит? Это означает, что для массива какой самый большой подмассив встречается в последовательности.

Например, arr = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
[13, -3, -25] является непрерывным подмассивом и
[20, -3, -16, -23] является непрерывным подмассивом

но [13, -25, -3] не потому, что это не произошло последовательно.

Если все значения в массиве положительны, какой будет самый большой подмассив? Это будет весь массив.

Почему?

представьте, что все массивы, которые мы используем, были положительными…

[13, 3, 25, 20 …] наибольшая сумма со всеми значениями вместе

Однако это будет не так просто. Массив может иметь и отрицательные значения.

Собираем все вместе

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

Если мы возьмем наш массив, разделим его на более мелкие подмассивы и решим их, мы получим меньшие решения. Что это значит? Если мы разделим массив на меньшие массивы и представим, что меньшие массивы были массивом для нашего вопроса, мы теперь решили меньшую проблему.

Как только мы решим эту меньшую подзадачу, мы соберем все вместе и решим большую проблему.

Чтобы разделить массив на более мелкие части, мы должны рекурсивно разделить массив равномерно по длине массива. У нас должна быть левая сторона и правая сторона. Почему? Потому что, когда мы разделим его поровну, у нас будет две части, левая и правая стороны.

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

Каким должен быть наш базовый случай? А что, если бы в массиве был только один элемент, каков наш максимум? Сам массив.

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

Мы знаем, что максимальное значение слева в нашем случае с использованием нашего массива подзадач ([13, -3]) вернет 13 слева и -3 справа для первых базовых случаев.

arr = [13, -3] (sub problem array)
left = 13
right = -3

Что это значит и как это помогает нам найти максимальный подмассив?

Потому что мы знаем, что нашли решение слева и нашли решение справа. Это половинки, нам еще предстоит рассмотреть решение, которое может возникнуть во всем массиве.

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

arr = [13, -3] (sub problem array)
left = 13 (MAX)
right = -3 (MAX)

Now consider the full subarray
[13, -3] if we add these would this become the largest subarry? No, but we still
need to consider it.
crossing = 10

Return max(left, right, crossing)

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

Ниже приведен код, написанный на JAVA.

public class MaximumSubArray {

 public static void main(String[] args) {
  int [] a = new int[]{
    13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7
  };
  Node res = maxSum(a, 0, 15);
  System.out.println("[begin: " + res.low  + " end: " + (res.high) + "] maxSum: " + res.sum);
 }
 
 public static class Node {
  int low;
  int high;
  int sum;

  public Node(int low, int high, int sum){
   this.low = low;
   this.high = high;
   this.sum = sum;
  }
 }

 private static Node maxSum(int[] arr, int low, int high) {
  if(high == low) {
   return new Node(low, high, arr[low]);
  }
  else {
   int mid = low + ((high-low)/2); 
   Node left = maxSum(arr, low, mid);
   Node right = maxSum(arr, mid+1, high);
   Node cross = cross(arr, low, mid, high);
   if(left.sum >= right.sum && left.sum>=cross.sum) {
    return left;
   } else if(right.sum >= left.sum && right.sum>=cross.sum) {
    return right;
   } else {
    return cross;
   }
  }
 }

 private static Node cross(int[] arr, int low, int mid, int high) {
  int leftSum = Integer.MIN_VALUE;
  int rightSum = Integer.MIN_VALUE;
  int sum = 0;
  int maxLeft = 0;
  int maxRight = 0;

  for(int i = mid; i>=low; i--) {
   sum = sum + arr[i];
   if(sum > leftSum) {
    leftSum = sum;
    maxLeft = i;
   }
  }
  
  sum = 0;
  for(int j = mid+1; j<=high; j++) {
   sum = sum + arr[j];
   if(sum > rightSum) {
    rightSum = sum;
    maxRight = j;
   }
  }
  
  return new Node(maxLeft, maxRight, leftSum+rightSum);
 }
}

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

Мы делаем это постоянно, пока не вернемся к исходному рекурсивному вызову, не выполним окончательное сравнение и не вернем максимальный подмассив.

Ссылки:
Кормен, Т. Х., Лейзерсон, К. Э., Ривест, Р. Л., и Штейн, К. (2009). Введение в алгоритмы. Мит Пресс.