Самый быстрый способ найти максимальный диапазон сумм в int []

Question

Был оптимизирован алгоритм и дошел до последней части. У меня есть массив целых чисел, как это:

[1, 1, 2, 5, 0, 5, 3, 1, 1]

Мое требование заключаются в следующем:

1. ввод: количество целых чисел, чтобы суммировать по
2. максимальная сумма должна состоять из целых чисел рядом друг с другим
3. , если целое число имеет значение 0 сумма в диапазоне будет недействительным
4. максимальная сумма целых чисел и индекс каждого целого возвращается

Ожидаемые результаты:

Учитывая вход 2 (2 хотел) с массивом, как упомянуто должен для этого вернуться [8, [ 5, 6]], где 8 - сумма целых чисел в индексе 5 и 6

Приведенный ввод 3 (3 раза) с массивом, как указано выше, для возврата [9, [5, 6, 7]], где 9 - сумма целых чисел в индексах 5, 6 и 7 (заметим, что хотя целые числа в индексах 3, 4, 5 имеют более высокую сумму t он недействителен, потому что индекс 4 равен 0)

В настоящее время я управляю этим, выполняя много циклов, но задавался вопросом, есть ли у кого-то лучший способ достичь этого. Мой язык кодирования по выбору в настоящее время является C# - я бы поэтому хотел, если бы возможные ответы были на C#. Любое использование linq и других модных функций Math в порядке, если это самый быстрый способ.

Answer 1

Думаю, вы можете решить это в линейном времени. Сначала замените все 0s на очень небольшое число (например, -2^30), чтобы оно не повлияло на нашу сумму.

Тогда:

let s[i] = sum of first i integers 
let k = number of integers required 
let max = -inf  
for (int i = k; i <= N; ++i) 
    if (s[i] - s[i - k - 1] > max) 
    max = s[i] - s[i - k - 1] 

Вы можете, вероятно, избежать замены нулей несколько дополнительных условий. если s [i] = сумма первых i целых чисел, то s [i] - s [k - 1] дает вам сумму целых чисел k через i.

Редактировать: Вы можете сделать это в дополнительном пространстве O (1) следующим образом: сначала заменить все 0s.

затем:

max = cr = sum of first k integers. 
for (int i = k + 1; i <= N; ++i) 
{ 
    cr = cr + numbers[i] - numbers[i - k] 
    if (cr > max) 
    max = cr; // also update positions 
} 

Чтобы избежать замены нулей в первом решении, просто пропустите K пространства впереди, сталкиваясь с нуля. Во втором решении пропустите k или k + 1 (в зависимости от того, как вы выбрали реализацию этого специального случая), но не забудьте перестроить свою переменную cr при выполнении пропусков!

Answer 2

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

int getSum(int[] arr, int wanted) 
     { 
      var pre = new int[arr.Length]; 
      pre[0] = 0; 
      pre[1] = arr[0]; 
      int max = 0; 
      int skip = 1; 
      for (var i = 1; i < arr.Length; i++) 
      { 
       skip--; 
       //if the sum is marked invalid with a zero skip 
       var current = arr[i]; 
       //calculate the index once 
       int preIndex = i + 1; 
       if (current == 0) 
       { 
        skip = wanted; 
        pre[preIndex] = pre[i]; 
        continue; 
       } 
       //store the sum of all elements until the current position 
       pre[preIndex] = pre[i] + current; 
       //find the lower end of the range under investigation now 
       var lower = i - wanted; 
       //if we haven't reached the wanted index yet we have no sum or if 
       //it's less than wanted element since we met a 0 
       //just go to the next element 
       if (lower < 0 || skip > 0) 
        continue; 
       var sum = pre[preIndex] - pre[lower]; 
       if (sum > max) 
        max = sum; 
      } 
      return max; 
     } 

Answer 3

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

using System; 
using System.Linq; 
public int[] max(int[] a, int amount) { 
    var max = int.MinValue; 
    var maxPos = 0; 
    if (a.length < amount) return null; 
    var c = 0; 
    while (c == 0) { 
     for (int i = 0; i < amount; i++) { 
      if (a[i + maxPos] == 0) { 
       c = 0; 
       break; // try again 
      } 
      c += a[i]; 
     } 
     if (c != 0) maxPos = i - amount; 
    } 
    if (c == 0) return null; 
    max = c; 
    for (int i = maxPos; i + amount < a.length; i++) { 
     if(a[i] == 0) { 
      i += amount - 1; 
      continue; 
     } 
     c -= a[i]; 
     c += a[i + amount]; 
     if (c > max) { 
      c = max; 
      maxPos = i; 
     } 
    } 
    if (c == 0) return null; 
    var result = new int[amount + 1]; 
    result[0] = max; 
    for (int i = 0; i < amount; i++) 
     result[i + 1] = maxPos + i; 
    return result; 
} 

Answer 4

Код "легко читается" считается "оптимизацией"?

int numberOfElements = 4; //parameter 
int[] numbers = new[] { 1, 1, 2, 5, 0, 5, 3, 1, 1 }; //numbers 


int[] result = 
    //cicle each element 
    (from n in Enumerable.Range(0, numbers.Length - numberOfElements + 1) 
    //keep the (n + numberOfElements) elements 
    let myNumbers = from p in Enumerable.Range(n, numberOfElements) 
        select numbers[p] 
    //keep the sum (if we got a 0, sum is 0) 
    let sum = myNumbers.Contains(0) ? 0 : myNumbers.Sum() 
    orderby sum descending  //order by sum 
    select myNumbers)   //select the list 
     .First().ToArray();  //first is the highest 

Рассмотрим добавление .AsParallel() для выполнения, когда .NET 4 выходит.

Answer 5

Идея 1. Разделить массив групп, чтобы измерить сумму 2. Count сумму для каждой группы 3. Рисунок из макс суммы

Вот код

private Result GetMax(ICollection<int> items, int itemCount) 
{ 
    return items. 
    Take(items.Count - (itemCount - 1)). 
    Select((value, index) => items.Skip(index).Take(itemCount)). 
    Select((group, index) => 
     new Result 
     { 
     Index = index, 
     Sum = group.Aggregate(0, (sum, i) => sum + (i == 0 ? int.MinValue : i)) 
     }). 
    Max(); 
} 

private struct Result : IComparable<Result> 
{ 
    public int Index { get; set; } 
    public int Sum { get; set; } 

    public int CompareTo(Result other) 
    { 
    return Sum.CompareTo(other.Sum); 
    } 
} 

Answer 6

Это O (n) времени и O (1) и проходит один раз через массив.

static public int[] FindMaxSumRange(int[] data, int n) 
{ 
    // two pointers showing the lower and upper bound of current running sum 
    int upper = 0, lower = 0; 
    // best result found yet 
    int max_found = 0; 
    int max_position = -1; 

    while (lower <= data.Length - n) { 
     int running_sum = 0; 
     // prefill running sum with n items 
     for (upper = lower; upper - lower < n && upper < data.Length; upper++) { 
      if (data[upper] == 0) { 
       // found a zero, set lower pointer to the next item 
       lower = upper + 1; 
       break; 
      } 
      running_sum += data[upper]; 
     } 
     if (upper - lower != n) { 
      // found a zero, restart at new lower position 
      continue; 
     } 
     if (running_sum > max_found) { 
      max_found = running_sum; 
      max_position = lower; 
     } 
     while (upper < data.Length) { 
      if (data[upper] == 0) { 
       // found a zero, set lower pointer to the next item 
       lower = upper; 
       break; 
      } 
      running_sum += data[upper] - data[lower]; 
      if (running_sum > max_found) { 
       max_found = running_sum; 
       max_position = lower; 
      } 
      upper++; lower++; 
     } 
     lower++; 
    } 
    return new int[]{max_found, max_position}; 
} 

Это возвращает максимальную сумму и позицию, в которой она была найдена. Если вам нужно получить список индексов, просто постройте диапазон [max_position, max_position + n)