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

Question

Существует массив целых чисел (как положительных, так и отрицательных). Пожалуйста, советьте алгоритм, который даст вам подмассиву с максимальной суммой. Пример:

int a[] = new int[]{2,3,-1,4,5,7,8,13,-20}; 

, то ответ должен быть {4,5,7,8,13}, как 4 + 5 + 7 + 8 + 13 = 37.

Я не могу разработать алгоритм для этой проблемы.

Answer 1

var a = [2,3,-1,4,5,7,8,13,-20]; 
var positiveNums = a.filter(function(num){ 
    return num > 0 
}); // [2,3,4,5,7,8,13] 
var sum = positiveNums.reduce(function(a, b){ 
    return a+b; 
}); // 42 

Answer 2

Вот линейное решение этой проблемы:

long getMaximumSubarraySum(int[] a) { 
    int start = 0; 
    int end = 0; 
    long result = 0; // I assume that an empty subarray is allowed. 
    long minPrefixSum = 0; 
    int minPrefixSumPos = -1; 
    long currentPrefixSum = 0; 
    for (int i = 0; i < a.length; i++) { 
     currentPrefixSum += a[i]; 
     if (currentPrefixSum - minPrefixSum > result) { 
      result = currentPrefixSum - minPrefixSum; 
      start = minPrefixSumPos + 1; 
      end = i + 1; 
     } 
     if (currentPrefixSum < minPrefixSum) { 
      minPrefixSum = currentPrefixSum; 
      minPrefixSumPos = i; 
     } 
    } 
    // The resulting subarray is [start; end). 
    return result; 
} 

Идея этого алгоритма очень проста: давайте посмотрим на префикс сумм. Тогда ответ будет максимальным значением max(prefixSum[i] - prefixSum[j]), где j < i для всех i. Это именно то, что делает этот код: он выполняет итерацию по входному массиву, поддерживает текущую префиксную сумму и минимальную сумму префикса и выбирает лучший ответ.

Answer 3

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

Основной момент программы заключается в том, что сумма уменьшается, когда вы сталкиваетесь с числовым числом в массиве. Поэтому, когда это произойдет, вы разделите массив на 3 части.
1) Сумма до сих пор
2) Сумма до сих пор + в negetive значение (или значения, если есть непрерывные negetive числа)
3) (2) + сумма, пока вы столкнетесь еще negetive номер

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

Вот псевдо-код:

do until end of array{ 
     b=compute_b() //Compute sum till you encounter negetive number 
     c=compute_c() //Compute sum till you encounter a positive number 
     a=max+b+c; 
     if(a>c) 
     { 
      if(a>max) 
      { 
         max=a; 
      } 
     } 
     else 
     { 
       if(c>max) 
       { 
        max=c; 
       } 
      } 
    } 
    print max