Kadane Máximo Subarrio -- # campo con algorithm camp codereview Relacionados El problema

Kadane maximum subarray


4
vote

problema

Español

Encuentre la suma máxima de Subarry con algoritmo de Kadane

  //test case  int maxKanade, startKanade, endKanade; maxKanade = Kadane(new List<int>() { 2, -4, 6, -3, 9 }, out startKanade, out endKanade); Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade); maxKanade = Kadane(new List<int>() { 3, 4, 6, -3, -9 }, out startKanade, out endKanade); Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade); //test case end  public static int Kadane(List<int> input, out int start, out int end) {     //from wiki https://en.wikipedia.org/wiki/Maximum_subarray_problem     //def max_subarray(A):     //max_ending_here = max_so_far = 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     start = 0;     int s = 0;     end = 0;     int count = 0;     int max_ending_here = 0, max_so_far = 0;     foreach(int i in input)     {         if (max_ending_here + i > 0)         {             max_ending_here += i;         }         else         {             // if go negative basically take a fresh start             max_ending_here = 0;             s = count + 1;         }         if (max_so_far < max_ending_here)         {             max_so_far = max_ending_here;             end = count;             start = s;         }         count++;     }     return max_so_far; }   
Original en ingles

Find the maximum sum of subarray with Kadane's algorithm

//test case  int maxKanade, startKanade, endKanade; maxKanade = Kadane(new List<int>() { 2, -4, 6, -3, 9 }, out startKanade, out endKanade); Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade); maxKanade = Kadane(new List<int>() { 3, 4, 6, -3, -9 }, out startKanade, out endKanade); Debug.WriteLine("{0} {1} {2}", maxKanade, startKanade, endKanade); //test case end  public static int Kadane(List<int> input, out int start, out int end) {     //from wiki https://en.wikipedia.org/wiki/Maximum_subarray_problem     //def max_subarray(A):     //max_ending_here = max_so_far = 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     start = 0;     int s = 0;     end = 0;     int count = 0;     int max_ending_here = 0, max_so_far = 0;     foreach(int i in input)     {         if (max_ending_here + i > 0)         {             max_ending_here += i;         }         else         {             // if go negative basically take a fresh start             max_ending_here = 0;             s = count + 1;         }         if (max_so_far < max_ending_here)         {             max_so_far = max_ending_here;             end = count;             start = s;         }         count++;     }     return max_so_far; } 
     
       
       

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

Podrías simplificar eso

  PascalCase5  

con

  PascalCase6  
 

You could simplify that

if (max_ending_here + i > 0) {     max_ending_here += i; } else {     // if go negative basically take a fresh start     max_ending_here = 0;     s = count + 1; } 

with

max_ending_here += i; if (max_ending_here <= 0) {     // if go negative basically take a fresh start     max_ending_here = 0;     s = count + 1; } 
 
 
 
 
2
 
vote

Pruebas
Cuando @ 200_success le preguntó si había probado el código que parecía desconcertado y señalaba que había incluido dos pruebas. Desafortunadamente, escribiendo cosas a la pantalla y la revisión de la vista, los resultados no se considerarían una buena prueba de la unidad y para un revisor, no son muy útiles, ya que todo lo que podemos decir es que se mostró alguna salida. No hay nada que indique cuáles fueron los resultados esperados o si se logró.

Además, dos pruebas de unidades que pasan son un subconjunto limitado para decir que está funcionando.

¿Qué sucede con una entrada vacía?
¿Qué pasa si todos son negativos?
¿Qué sucede si tenemos dos submarinos que ambos tienen el mismo valor máximo?

  • En un grado, esta es una brecha en los requisitos, el original Kadane solo se preocupa por el valor máximo, no el inicio y el final.

Deberíamos devolver start = 0 y end1 = 0 Si no hay elementos en la entrada o si todos son negativos. El resultado (0) es correcto, pero parece indicar una matriz de longitud que comienza en 0, que termina a 0.

LÍNEA INFERIOR: probar una función como este es un gran lugar para usar un marco de prueba de unidad automatizado. Puede parecer que duplique el código que debe escribirse, pero en el momento en que uno ha ejecutado el código, lea y revisó las respuestas y se repitió los tiempos de inmóvil por cada ajuste al código para tratar la siguiente cosa que no habíamos pensado, lo hace. Ahorre tiempo y le da una buena sensación borrosa que podemos ver que funciona y, si hay cambios se rompe.

api
No utilizamos la funcionalidad 99887766655443322 en cualquier lugar de la función, pero insista en que el usuario pasa en un 9988776665544333 . Presionaría para cambiar la interfaz a IEnumerable<int> .

 

Testing
When @200_success asked if you had tested the code you seemed puzzled and pointed out that you had included two tests. Unfortunately, writing things out to the screen and sight checking the results would not be considered good unit testing and for a reviewer they are not very useful as all we can tell is that some output was displayed. There is nothing to indicate what the expected results were or if they were achieved.

Also, two unit tests which pass is a limited subset to say that it is working.

What happens with an empty input?
What happens if they are all negative?
What happens if we have two sub-arrays which both have the same maximum value?

  • to a degree this is a gap in the requirements, the original Kadane only cares about the max value not the start and end.

Should we return start = 0 and end = 0 if there are no elements in the input or if all are negative. The result (0) is correct but it seems to indicate an array of length starting at 0, ending at 0.

Bottom line: Testing a function like this is a great place to use an automated unit testing framework. It may seem like doubling the code to be written but by the time one has run the code, read and checked the answers and repeated umpteen times for each tweak to the code to deal with the next thing we hadn't thought of, it does save time and gives a nice warm fuzzy feeling that we can see that it works and if any changes break it.

API
We do not use the List functionality anywhere in the function but insist that the user passes in a List. I would push for changing the interface to IEnumerable<int>.

 
 
 
 
2
 
vote

una pequeña contribución. Este bloque de código se ve un poco desagradable:

  start = 0; int s = 0; end = 0; int count = 0; int max_ending_here = 0, max_so_far = 0;   

Tienes dos estilos de declaración, diría que Mezcling ellos arriba no es "de moda" - Supongo que es la palabra?

Podrías ir con algo así:

  start = 0; end = 0; int s, count, max_ending_here, max_so_far = 0;   

o

  start = 0; end = 0; int s = 0; int count = 0; int max_ending_here = 0; int max_so_far = 0;   
 

A small contribution. This code block looks a bit unpleasant:

start = 0; int s = 0; end = 0; int count = 0; int max_ending_here = 0, max_so_far = 0; 

You have two declaration styles, I would say that mixing them up isn't "fashionable" -- I guess is the word?

You could go with something like:

start = 0; end = 0; int s, count, max_ending_here, max_so_far = 0; 

or

start = 0; end = 0; int s = 0; int count = 0; int max_ending_here = 0; int max_so_far = 0; 
 
 
1
 
vote

puede mover la verificación en max_so_far en el interior del max_ending_here += i;
No hay razón para procesar 0

  end0  
 

Can move the check on max_so_far to inside the max_ending_here += i;
No reason to process 0

foreach(int i in input) {     if (i == 0)     { }     else if (max_ending_here + i > 0)     {         max_ending_here += i;         if (max_so_far < max_ending_here)         {             max_so_far = max_ending_here;             end = count;             start = s;         }     }     else     {         // if go negative basically take a fresh start         max_ending_here = 0;         s = count + 1;     }            count++; } 
 
 

Relacionados problema

25  Algoritmo para transformar una palabra a otra a través de palabras válidas  ( Algorithm to transform one word to another through valid words ) 
He estado practicando retroceso y quería saber cómo puedo mejorar mi código. Por ejemplo, no quiero usarlo global. Además, no estoy seguro de si mi código fun...

5  Proyecto EULER NO. 17: contando letras para escribir los números de 1 a 1000  ( Project euler no 17 counting letters to write the numbers from 1 to 1000 ) 
Soy muy nuevo en la programación y, cierto, estoy avergonzado de compartir mi código para la crítica. Este código funciona y produce la respuesta correcta a l...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

8  Simple GCD Utility en Java  ( Simple gcd utility in java ) 
i anteriormente discutido El rendimiento se refiere a diferentes algoritmos GCD. Escribí una simple clase de Java que implementa el algoritmo binario GCD. E...

35  Demasiados bucles en la aplicación de dibujo  ( Too many loops in drawing app ) 
Tengo un método que tiene muchos bucles: #ifndef __RUNES_STRUCTURES_H #define __RUNES_STRUCTURES_H /* Runes structures. */ struct Game { char board[2...

6  Encontrar el siguiente palíndromo de una cadena de números  ( Finding the next palindrome of a number string ) 
Aquí está el problema: Un entero positivo se llama palíndromo si su representación en el El sistema decimal es el mismo cuando se lee de izquierda a dere...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...

5  Orden de número más grande en cadena  ( Largest number order in string ) 
Dada una cadena, suponiendo que la cadena sea solo números, reorganice la cadena a la que sea el mayor número posible. a continuación es mi solución al pr...

1  Retire todos los nodos que no se encuentren en ningún camino con suma> = k  ( Remove all nodes which dont lie in any path with sum k ) 
Dado un árbol binario, una ruta completa se define como un camino desde la raíz a una hoja. La suma de todos los nodos en ese camino se define como la suma d...

56  Proyecto Euler Problema 1 en Python - Múltiples de 3 y 5  ( Project euler problem 1 in python multiples of 3 and 5 ) 
Me gustaría sugerencias para optimizar esta solución de fuerza bruta a problema 1 . El algoritmo actualmente comprueba cada entero entre 3 y 1000. Me gustarí...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos