Как найти максимальное непрерывное SUM в массиве (который содержит положительные и отрицательные числа)?

Question

Я хочу написать функцию ContigSum(i,j), которая вычисляет сумму смежных элементов от a[i] до a[j], где i<=j и a[] содержат положительные и отрицательные числа.

Не могли бы вы сказать мне эффективное время, чтобы найти максимизированный непрерывный SUM в массиве?

Answer 1

Хорошо объяснено в записи в википедии о предмете.Я нахожу код Python (т. Е. Исполняемый псевдокод), который они дают для алгоритма Кандана, немного жемчужины:

def max_subarray(A):
    max_so_far = max_ending_here = 0
    for x in A:
        max_ending_here = max(0, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Answer 2

Это обсуждается в столбце 7 1-го издания или в столбце 8 2-го издания « Programming Pearls » Джона Бентли.

Answer 3

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

Конечно, в оригинальном алгоритме Кадана можно получить начальный и конечный индексы подмассива, что полезно для определения «пути».:

def max_subarray(A):
    (maxSum, maxStartIndex, maxEndIndex) = (float("-inf"), 0, 0)
    (currentMaxSum,currentStartIndex,currentEndIndex ) = (0,0,0)

    for item in A: 
        currentMaxSum = currentMaxSum + item
        if currentMaxSum > maxSum :
            (maxSum, maxStartIndex, maxEndIndex) = (currentMaxSum, currentStartIndex, currentEndIndex)
        if currentMaxSum < 0 :
            currentMaxSum = 0
            currentStartIndex = currentEndIndex + 1

        # continue here.
        currentEndIndex = currentEndIndex + 1

    return (maxSum, maxStartIndex, maxEndIndex)

Answer 4

Вот мое решение в Ruby. Вернуть максимальную непрерывную сумму в O (n) времени и O (1) памяти. Я также написал несколько юнит-тестов на всякий случай;)

def largest_contiguous_subsum(array)
  max_sum = 0
  current_sum = 0
  array.each do |num|
    current_sum += num
    max_sum = current_sum if current_sum >= max_sum
    current_sum = 0 if current_sum < 0
  end

  return max_sum
end

Answer 5

Вот код C ++, который я только что реализовал и протестировал в Visual Studio 2012.

int maxSum(int *A, int lo, int hi)  {
    int left = lo, right = lo, sum = INT_MIN, currentMaxSum = 0, maxLeft = lo, maxRight = lo;
    for(int i = lo; i < hi; i++)    {
        currentMaxSum += A[i];
        if(currentMaxSum > sum) {
            sum = currentMaxSum;
            right = i;
            maxLeft = left;
            maxRight = right;
        }
        if(currentMaxSum < 0)   {
            left = i+1;
            right = left;
            currentMaxSum = 0;
        }
    }
    printf("Maximum sum contiguous subarray :");
    for(int i = maxLeft; i <= maxRight; i++)
        printf(" %d", A[i]);
    printf("\n");
    return sum;
}

Ниже приведен код main () для вызова вышеуказанной функции.

int main()  {
    int A[] = {3,-4, -3, 2, 6};
    int N = sizeof(A) / sizeof(int);

    printf("Maximum sum : %d\n", maxSum(A, 0, N));

    return 0;
}

Answer 6

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

Answer 7

static void MaxContiguousSum(int[] x, int lb, int[] result)
{
    int start, end, sum, testSum;

    start = lb;
    end = lb;

    /* Empty vector has 0 sum*/
    sum = 0;

    testSum = 0;
    for (int i=lb; i < x.length; i++)
    {
        if (sum + x[i] < 0)
        {
            /* Net contribution by current term is negative. So, contiguous sum lies in [start,i-1] 
              or [i+1, array upper bound]*/
            MaxContiguousSum(x, i+1, result);

            if (result[0] < sum)
            {
                result[0] = sum;
                result[1] = start;
                result[2] = end;
            }
            return;

        }
        else
        {
            testSum += x[i];

            if (testSum > 0)
            {
                /* Move the end marker since incrementing range is beneficial. */
                end = i;

                /* update the sum*/
                sum += testSum;

                /* reset the testSum */
                testSum = 0;
            }
        }

    }

    /* Update the results */
    result[0] = sum;
    result[1] = start;
    result[2] = end;

    return;


}