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

Question

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

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

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

1. input: количество целых чисел для суммирования по
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 имеют более высокую сумму, результат является недействительным из-за индекса 4 будучи 0)

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

Answer 1

Я думаю, вы можете решить это за линейное время. Сначала замените все 0 на очень маленькое число (например, -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) дополнительном пространстве следующим образом: сначала заменить все 0.

, то:

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

Это 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)

Answer 3

Считается ли «легко читаемый» код «оптимизацией»?

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 4

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

 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 5

Идея есть 1. Разделить массив на группы для измерения суммы 2. Подсчитайте сумму для каждой группы 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

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

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;
}