순서가 지정된 양의 정수리스트에서 가장 큰 양의 델타 찾기

Question

나는 몇 시간에 걸쳐 팀의 성과가 가장 최근의 시간에서부터 실행되는 다양한 테이블에 비해 순위가 매겨지는 순위 표를 보는 파이썬 스크립트를 작성하고 있습니다. , like

 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 

내가 원하는 것은 모든 팀에서 가장 큰 긍정적 개선점입니다. 내가 원하지 않는 것은 가장 큰 델타는 12.

경우에도, 그래서

Team C: 30 18 20 

최대 규모의 상승은 2가는 팀, 가장 높은 지점에 최소의 절대 값 위의 A의 경우 가장 큰 상승은 # 16 (7 시즌 전)부터 이번 시즌 # 10까지이며, B의 경우 최대 상승은 # 22에서 # 7까지, 11 년과 6 시즌 전입니다.

이 같은 목록을 통해 루프를 원하고, 그때 가장 큰 긍정적 인 INT 저장) (각 시즌 팝업 및 이전의 모든 계절에서 뺄 수

Team A: 6 
Team B: 15 

같은 것을 반환하지만 지저분한 느낌. OTOH, 목록을 정렬하고 첫 번째 요소와 마지막 요소를 가져 오면 순위 하락이 표시됩니다. (나는 손실만을 측정하지 않고 이득을 측정하고 싶습니다.)

시즌 실적의 배열을 취하는 간단한 방법은 최근의 좋은 팀 성과 이전의 가장 나쁜 성능 사이의 가장 큰 차이를 루프없이 찾아내는 것입니까?

Answer 1

목록을 반복하면서 최소값과 현재 최대 상승 값 (current list member - min)을 추적해야합니다. 리스트 멤버를 처리 할 때마다 새로운 min인지 확인하고 필요에 따라 현재 가장 큰 상승을 업데이트하십시오.

이전 시즌을 모두 감산 할 필요는 없지만 새로운 요소가 새로운 최소값인지, 가장 큰 요소인지 아직 확인해야합니다.

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 

모든 요소에 대해 반복되는 O (n)의 시간 복잡도.

목표와 목록을 뒤집지 만 결과는 같습니다. 즉. 나는 현재의 해에서 과거의 것뿐만 아니라 더 높은 순위에서 낮은 것까지도 갈 것입니다.

Answer 2

아주 예쁜하지,하지만 난 당신이 가장 큰 개선의 순서를 식별 할 수 있다고 생각 :

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)