максимальный подмассив массива с целыми числами

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

def get_max_sum_subset(x): max_subset_sum = 0 max_subset_i = 0 max_subset_j = 0 for i in range(0,len(x)+1): for j in range(i+1,len(x)+1): current_sum = sum(x[i:j]) if current_sum > max_subset_sum: max_subset_sum = current_sum max_subset_i = i max_subset_j = j return max_subset_sum,max_subset_i,max_subset_j 

Ваше решение – O (n ^ 2). Оптимальное решение линейно. Он работает так, что вы просматриваете массив слева направо, принимая во внимание лучшую сумму и текущую сумму:

 def get_max_sum_subset(x): bestSoFar = 0 bestNow = 0 bestStartIndexSoFar = -1 bestStopIndexSoFar = -1 bestStartIndexNow = -1 for i in xrange(len(x)): value = bestNow + x[i] if value > 0: if bestNow == 0: bestStartIndexNow = i bestNow = value else: bestNow = 0 if bestNow > bestSoFar: bestSoFar = bestNow bestStopIndexSoFar = i bestStartIndexSoFar = bestStartIndexNow return bestSoFar, bestStartIndexSoFar, bestStopIndexSoFar 

Эта проблема также обсуждалась в « Программировании жемчуга: методы проектирования алгоритмов» (настоятельно рекомендуется). Там вы также можете найти рекурсивное решение, которое не является оптимальным (O (n log n)), но лучше, чем O (n ^ 2).

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

Первое, что нужно отметить, это то, что максимальный субарей (который должен быть смежной частью данного массива A), заканчивающийся в позиции j, либо состоит из максимального субарама, заканчивающегося в позиции j-1 плюс A [j], либо пуст (это только если A [j] <0). Другими словами, мы спрашиваем, положительно ли элемент A [j] положительно влияет на текущую максимальную сумму, заканчивающуюся в позиции j-1. Если да, включите его в максимальный субарак; если нет, то нет. Таким образом, от решения меньших подзадач, которые перекрываются, мы можем создать оптимальное решение.

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

 sum[0] = max(0, A[0]) sum[j] = max(0, sum[j-1] + A[j]) 

Мы можем построить эти ответы снизу вверх, сканируя A слева направо. Мы обновляем сумму [j], поскольку мы рассматриваем A [j]. Мы также можем отслеживать общее максимальное значение и местоположение максимального подмашины в этом процессе. Вот краткое решение, которое я написал в Ruby:

 def max_subarray(a) sum = [0] max, head, tail = sum[0], -1, -1 cur_head = 0 (0...a.size).each do |j| # base case included below since sum[-1] = sum[0] sum[j] = [0, sum[j-1] + a[j]].max cur_head = j if sum[j-1] == 0 if sum[j] > max max, head, tail = sum[j], cur_head, j end end return max, head, tail end 

Взгляните на мой смысл, если вы хотите проверить это для себя.

Это, очевидно, линейный алгоритм O (N), поскольку требуется только один проход по списку. Надеюсь это поможет!

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

пусть n – количество элементов, a(i) – ваш массив f(i) – максимальная сумма подмассива, которая заканчивается в позиции i (минимальная длина равна 1). Затем:

 f(0) = a(i); f(i) = max(f(i-1), 0) + a(i); //f(i-1) when we continue subarray, or 0 - when start at i position 

max(0, f(1), f(2), ... , f(n-1)) – ответ

Существует короткое видео из MIT, которое помогает вам понять эту проблему динамического программирования. http://people.csail.mit.edu/bdean/6.046/dp/ Нажмите на первую ссылку в разделе «Проблемы», и вы увидите ее.

Вот простой алгоритм O (N) из http://en.wikipedia.org/wiki/Maximum_subarray_problem

 int maxsofar=0; int maxendinghere=0; for i=[0 n] { maxendinghere=max(maxendinghere+x[i],0); maxsofar=max(maxsofar,maxendinghere); } 

Если мне не хватает чего-то важного, если они являются целыми положительными, подмножество будет включать весь массив, если они являются целыми числами, он будет включать только положительные целые числа. Есть ли еще какое-то ограничение?

Решение Java:

Не работает для массива со всеми негативами.

 public static int[] maxsubarray(int[] array) { //empty array check if (array.length == 0){ return new int[]{}; } int max = 0; int maxsofar = 0; //indices int maxsofarstart = 0; int maxsofarend = 0; int maxstartindex = 0; for (int i = 0; i < array.length; i++) { if (array[i] > 0) { if (max == 0) { maxstartindex = i; } max = max + array[i]; if (max > maxsofar) { maxsofar = max; maxsofarstart = maxstartindex; maxsofarend = i; } } else { max = 0; } } return Arrays.copyOfRange(array, maxsofarstart, maxsofarend + 1); } 

вот одно из наиболее хорошо выработанных, проверенных, работающих решений – http://rerun.me/blog/2012/08/30/maximum-continuous-subarray-problem-kandanes-algorithm/

 package me.rerun; public class Kadane { public static void main(String[] args) { int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 }; //int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3}; //int[] intArr={-6,-2,-3,-4,-1,-5,-5}; findMaxSubArray(intArr); } public static void findMaxSubArray(int[] inputArray){ int maxStartIndex=0; int maxEndIndex=0; int maxSum = Integer.MIN_VALUE; int cumulativeSum= 0; int maxStartIndexUntilNow=0; for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) { int eachArrayItem = inputArray[currentIndex]; cumulativeSum+=eachArrayItem; if(cumulativeSum>maxSum){ maxSum = cumulativeSum; maxStartIndex=maxStartIndexUntilNow; maxEndIndex = currentIndex; } else if (cumulativeSum<0){ maxStartIndexUntilNow=currentIndex+1; cumulativeSum=0; } } System.out.println("Max sum : "+maxSum); System.out.println("Max start index : "+maxStartIndex); System.out.println("Max end index : "+maxEndIndex); } } 

Это правильный Java-код, который будет обрабатывать сценарии, включая все отрицательные числа.

 public static long[] leftToISumMaximize(int N, long[] D) { long[] result = new long[N]; result[0] = D[0]; long currMax = D[0]; for (int i = 1; i < N; i++) { currMax = Math.max(D[i], currMax + D[i]); result[i] = Math.max(result[i - 1], currMax); } return result; } 

Существует простой алгоритм динамического программирования для задачи максимального субарама, которая выполняется в O (N): алгоритм Кадана . Небольшие изменения в базовом алгоритме позволят вам обрабатывать все отрицательные числа: следует ли возвращать наибольшее число или 0.

Не уверен, но принятое решение не предназначалось для меня для всех сценариев (возможно, я его неправильно понял). Поэтому я сделал небольшую модификацию, а не if (value> 0), я изменил ее yo if (value> bestNow)

 .....(I wrote it in Scala) 

И он работает для всех сценариев

 def findMaxSubArray(list: List[Int]): (Int, Int, Int) = { var (bestNow,bestSoFar) = (0, 0) var ( startIndexNow, startIndexSoFar, endIndex) = (-1, -1, -1) for (i <- 0 until list.length) { var value = bestNow + list(i) if (value > bestNow) { if (bestNow == 0) startIndexNow = i bestNow = value } else bestNow = 0 if (bestNow > bestSoFar) { bestSoFar = bestNow startIndexSoFar = startIndexNow endIndex = i } } return (bestSoFar, startIndexSoFar, endIndex) } def main(args: Array[String]) { println(findMaxSubArray(List(3, -1, 5, 3, -6, -9, 6, 1)).toString) println(findMaxSubArray(List(3, -1, 5, 3, -6, -9, 6, 3)).toString) println(findMaxSubArray(List(20, -1, 5, 3, -6, -9, 6)).toString) } Output..... (max =8, start=2, end=3) (max=9, start=6, end=7) (max=20, start=0, end= 0) 

Я сделал функцию для более общей проблемы:

  • Найдите максимальный субарм суммы (что означает его границы и сумму, а не только сумму)
  • Если два подмассива имеют равные суммы, то выберите более короткий
  • Если два одинаково длинных подмассива имеют равные суммы, то выберите тот, который появляется первым.

Функция основана на алгоритме Кадане и работает в O (n) времени. В принципе, это он:

 function MaxSumSubarray(a, n, start out, len out) -- a - Array -- n - Length of the array -- start - On output starting position of largest subarray -- len - On output length of largest subarray -- Returns sum of the largest subarray begin start = 0 len = 1 int sum = a[0] curStart = 0 curLen = 1 curSum = a[0] for i = 2 to n begin if a[i] >= curSum + a[i] then begin curStart = i curLen = 1 curSum = a[i] end else begin curLen = curLen + 1 curSum = curSum + a[i] end if (curSum > sum) OR (curSum = sum AND curLen < len) OR (curSum = sum AND curLen = len AND curStart < start) then begin start = curStart len = curLen sum = curSum end end return sum end 

Я загрузил все решение на C # с помощью анализа и примеров в этой статье: Maximum Sub Subarray

  • C ++ Эффективное вычисление текущей медианы
  • Объясните, как работает узел запуска цикла в циклическом списке?
  • искать интервальное перекрытие в списке интервалов?
  • Алгоритм: эффективный способ удаления повторяющихся целых чисел из массива
  • Преобразование равномерного распределения в нормальное распределение
  • Наибольший круг внутри невыпуклого многоугольника
  • Планарные графы
  • Как проверить, являются ли два слова анаграммами
  • Вычисление множества пересечений в линейном времени?
  • Как работают тригонометрические функции?
  • Как вычислить точку на окружности круга?
  • Давайте будем гением компьютера.