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

Ответ 1

Ваше решение - 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

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

Ответ 2

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

Первое, что нужно отметить, это то, что максимальный субарак (который должен быть смежной частью данного массива A), заканчивающийся в позиции j, либо состоит из максимального субарара, заканчивающегося в позиции j-1 плюс A [j], либо empty (это происходит только, если 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

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

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

Ответ 3

let 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)) - ответ

Ответ 4

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

Ответ 5

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

Ответ 6

Вот простой алгоритм 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);
}

Ответ 7

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

Ответ 8

Решение 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);

}

Ответ 9

вот одно из наиболее хорошо протестированных, работающих решений - 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);
}

}

Ответ 10

Это правильный код 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;
}

Ответ 11

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

Ответ 12

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

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

Функция основана на алгоритме Кадане и работает в 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

Я загрузил все решение на С# с помощью анализа и примеров в этой статье: Максимальный субарм суммы

Ответ 13

Не уверен, но принятое решение не предназначалось для меня для всех сценариев (может быть, я его неправильно понял) Поэтому я сделал небольшую модификацию, вместо   if (значение > 0) Я изменил его лет   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)