Trouver le plus grand delta positif dans une liste ordonnée d'entiers positifs

Question

J'écris un script python pour regarder une table de classement, où la performance d'une équipe sur plusieurs saisons est classée par rapport à d'autres, à partir du plus récent retour dans le temps , comme

 Latest ->          <- Earliest 
Team A: 10 10 12 12 13 13 13 14 15 14 16 13 11 15 14  
Team B: 14 14 15 16 15 7 14 14 15 10 22 15 15 11 16 

Ce que je veux est la plus grande amélioration positive, sur toute période de temps, pour chaque équipe. Ce que je ne veux pas, c'est la valeur absolue du plus bas au plus haut point, donc pour une équipe qui va

la plus forte hausse est à seulement 2, même si le plus grand delta est 12.

Dans le Dans le cas A ci-dessus, la plus forte hausse est de # 16 (il y a 7 saisons) à # 10 cette saison, alors que pour B, la plus forte hausse va de # 22 à # 7 entre 11 et 6 saisons.

Je veux faire une boucle sur une liste comme ça, et retourne quelque chose comme

Team A: 6 
Team B: 15 

je pouvais pop() chaque saison, et le soustraire de toutes les saisons précédentes, puis enregistrez le plus grand int positif, mais se sent malpropre. OTOH, en triant la liste et en tirant les premier et dernier éléments ferait apparaître des déclins dans le classement aussi bien. (Je veux seulement mesurer les gains, pas les pertes.)

Existe-t-il un moyen simple de prendre en compte l'ensemble des performances saisonnières? Trouvez le plus grand delta entre une performance récente, une bonne performance d'équipe et une performance antérieure moins bonne sans boucle?

Answer 1

Vous devez effectuer une boucle sur la liste, garder la trace de la valeur min et la plus grande augmentation actuelle (qui est le current list member - min). Chaque fois que vous traitez un membre de la liste, vérifiez s'il s'agit de la nouvelle min et mettez à jour la plus grande augmentation actuelle selon vos besoins.

Vous n'avez pas besoin de soustraire de toutes les saisons précédentes, il vous suffit de vérifier si le nouvel élément est le nouveau minimum et s'il fait la plus grande augmentation pour le moment.

Ex.

def find_max_pos_delta(my_scores): 
    my_list = map(int, my_scores.strip().split()) 
    my_min = current_largest = None 
    for rank in my_list: 
     if my_min is None or rank < my_min: 
      my_min = rank 
     new_largest = rank - my_min 
     if current_largest is None or new_largest > current_largest: 
      current_largest = new_largest 

    return current_largest 

assert find_max_pos_delta('30 18 20') == 2 
assert find_max_pos_delta('10 10 12 12 13 13 13 14 15 14 16 13 11 15 14 ') == 6 
assert find_max_pos_delta('14 14 15 16 15 7 14 14 15 10 22 15 15 11 16') == 15 

La complexité temporelle O (n) lorsqu'elle boucle sur tous les éléments.

Notez que j'ai choisi d'inverser le but et la liste mais le résultat est le même. c'est à dire. Je vais de l'année en cours au passé mais aussi d'un rang supérieur à un rang inférieur.

Answer 2

Pas très jolie, mais je crois que vous pouvez identifier la plus grande séquence avec amélioration:

def find_greatest_rise(rank_list): 
    rank_list = rank_list[::-1] #reverse the rank list so we iterate moving forward in time 
    i = 0 
    if len(rank_list) > i + 1: 
     bottom = 0 
     top = 0 
     delta = 0 
     end_of_list = False 

     while not end_of_list: 
      curr_rank = rank_list[i] 
      for j, r in enumerate(rank_list[i + 1:]): 
       if curr_rank - r > 0: 
        if curr_rank - r >= delta: 
         delta = curr_rank - r 
         bottom = curr_rank 
         top = r 
       else: 
        i += j + 1 
        break 

       if j == len(rank_list[i + 1:]) - 1: 
        end_of_list = True 

     print "bottom: {}, top: {}, delta: {}".format(bottom, top, delta)