La forma más rápida de encontrar el rango de suma máxima en int []

Question

Se ha optimizado un algoritmo y se ha llegado a la última parte. Tengo una matriz de enteros como esto:

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

Mi requisito son los siguientes:

1. de entrada: número de números enteros a suma sobre
2. la suma max debe consistir en números enteros uno junto al otro
3. si un número entero tiene el valor 0 la suma en el rango no sería válida
4. la suma máxima de números enteros y el índice de cada número entero se devuelve

Resultados esperados:

entrada dada de 2 (2 queríamos) con la matriz como se ha mencionado debe para ello volver [8, [ 5, 6]] donde 8 es la suma de números enteros en el índice 5 y 6

Dada la entrada de 3 (3 buscados) con la matriz como se menciona debe entonces devolver [9, [5, 6, 7]] donde 9 es la suma de enteros en los índices 5, 6 y 7 (observe que aunque los enteros en los índices 3, 4, 5 tienen una suma más alta t El resultado es inválido debido a que el índice 4 es 0)

Actualmente estoy manejando esto haciendo muchos bucles, pero me preguntaba si alguien tenía una mejor manera de lograr esto. Mi lenguaje de programación de elección es actualmente C# - Por lo tanto, agradecería si las respuestas posibles estuvieran en C#. Cualquier uso de linq y otras características de fantasía de matemáticas está bien, siempre que sea la manera más rápida.

Answer 1

Creo que puede resolver esto en tiempo lineal. Primero, reemplace todos los 0 con un número muy pequeño (-2^30 por ejemplo) para que no afecte a nuestra suma.

continuación:

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] 

es probable que pueda evitar la sustitución de ceros con algunas condiciones adicionales. si s [i] = suma de los primeros i enteros, entonces s [i] - s [k - 1] le da la suma de los enteros k hasta i.

Editar: Puedes hacer esto en O (1) espacio extra como este: primero reemplaza todos los 0s.

entonces:

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 
} 

Para evitar la sustitución de ceros en la primera solución, omita espacios k delante cuando se encuentra con un cero. En la segunda solución, omita k o k + 1 (depende de cómo elija implementar este caso especial) espacios por delante, ¡pero asegúrese de reconstruir su variable cr al hacer el salto!

Answer 2

El siguiente código debería hacer el truco. El rendimiento dependerá del tamaño del rango que se sumará. Los más elemnts la mejor se llevará a cabo en comparación con el ingenuo de la adición de un subconjunto en cada iteración

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

Lo siguiente fue una queja, y totalmente no probado. Ni siquiera estoy seguro de si se compilará.Dejo que otros lo mejoren.

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

¿El código "fácil de leer" se considera una "optimización"?

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 

considerar la adición de un .AsParallel() de rendimiento cuando .NET 4 ya está disponible.

Answer 5

Idea es 1. array Split a grupos para medir suma suma 2. Contador para cada grupo 3. Figura cabo suma max

Aquí está el código

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

Esto es O (n) tiempo y O (1) espacio y va solo una vez a través de la matriz.

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

Esto devuelve la suma máxima y la posición en la que se encontró. Si necesita obtener una lista de los índices, solo cree el rango [max_position, max_position + n)