시퀀스에서 최대 길이의 서브 시퀀스 추출하기 [PYTHON]

Question

값 시퀀스가 ​​[1,2,3,4,1,5,1,6,7]이며, 가장 긴 서브 시퀀스를 찾아야합니다. 길이 증가. 그러나 함수가 이전 수보다 낮은 수에 도달하면 함수는 계산을 중지해야합니다. 이 경우이 순서의 대답은 [1,2,3,4]입니다. 리셋되기 전에 4 개의 값을 가지고 있습니다. 어떻게 파이썬 코드를 작성하겠습니까?

참고 : "가장 길게 증가하는 서브 시퀀스"를 찾는 것이 일반적인 문제인 것처럼 보이므로 온라인 검색에서는 시퀀스의 전체 길이에 대해 계산할 많은 솔루션을 찾았으며 값을 증가시키는 하위 시퀀스를 반환합니다. 감소하므로이 경우 [1,2,3,4,5,6,7]을 반환합니다. 그건 내가 찾는 것이 아니다.

각 하위 시퀀스를 세고 이전 수보다 낮은 수에 도달하면 카운트를 다시 설정해야합니다. 그런 다음 계산 된 모든 하위 시퀀스를 비교하고 가장 긴 시퀀스를 반환해야합니다.

미리 감사드립니다.

Answer 1

b = [4,1,6,3,4,5,6,7,3,9,1,0] 

def findsub(a): 
    start = -1 
    count = 0 
    cur = a[0] 
    for i, n in enumerate(a): 
    if n is cur+1: 
     if start is -1: 
     start = i - 2 
     count=1 
     count+=1 
     cur = n 
    if n < cur and count > 1: 
     return [a[j] for j in range(start,start+count+1)] 


print findsub(b) 

다소 엉성한 알고리즘이지만 원하는대로하는 것으로 생각됩니다. 일반적으로 나는 단순히 코드를 보여주지 않았지만, 그것이 당신이 원했던 것임을 의심하고, 당신이 그것을 배우고, 배운 것을 통해 자신 만의 것을 만들 수 있기를 바랍니다.

b = [1,2,0,1,2,3,4,5] 

def findsub(a): 
    answer = [a[0]] 
    for i in a[1:]: 
    if answer[-1] + 1 is i: 
     answer.append(i) 
    if not len(answer) > 1: 
     answer = [i] 
    elif i < answer[-1] and len(answer) > 1: 
     return answer 
    return answer 



print findsub(b) 

Answer 2

당신은 다음을 수행해야합니다 :

나는 그것을 좋아하지 않았기 때문에 약간 더 나은 찾는 방법

,

1. 목록이 제공하는 기능 W를 만들기 인덱스를 반환 목록의 처음부터 엄격하게 증가하지 않는 마지막 항목의 예를 들어

   • 다음 목록 주어진 : [1,2,3,4,1,2,3], [4,2,1], [5,6,7,8] 그것은

2. 변수 maxim 만들기 각 목록은 각각 4, 1, 4를 복귀 0

3. 에 값을 설정해야 목록이 비어있을 때까지 반복적으로 수행하십시오.
   • 목록에 기능 W에 전화를 걸어 x보다 큰 maxim
     • 는이 순서를 저장하고자하는 경우, 당신이 사용할 수있는이 시점에서 x
     • 에 maxim을 설정하는 경우의 반환 값을 x
     • 를 부르 자 list-slice notation은 시퀀스가 ​​포함 된 목록의 해당 부분을 가져옵니다.
   • 가장 긴 시퀀스가 ​​포함 된 목록의 일부를 저장 한 경우

마지막으로, 인쇄 maxim하고, 당신이있어 마지막을 인쇄 목록에서 목록의 해당 부분을 삭제

Answer 3

가능한 모든 오름차순 부분 시퀀스를 생성하는 함수를 생각해보십시오. 빈 목록으로 시작하여 한 요소가 더 작거나 (?와 같을 때까지) 항목을 추가하고 이전 위치에서 하위 시퀀스를 저장하고 (yield) 새로운 하위 시퀀스가있는 estart.

1. 그래서 우리가 할 수 를 발생시키는 발전기에게 StopIteration 요구 사항을 완료하려면 : 빈 시퀀스의 처리에 대한

   def all_ascending_subsequences(sequence): 
       #use an iterator so we can pull out the first element without slicing 
       seq = iter(sequence) 
   
       try: #NOTE 1 
        last = next(seq) # grab the first element from the sequence 
       except StopIteration: # or if there are none just return 
        #yield [] #NOTE 2 
        return 
   
       sub = [last] 
       for value in seq: 
        if value > last: #or check if their difference is exactly 1 etc. 
         sub.append(value) 
        else: #end of the subsequence, yield it and reset sub 
         yield sub 
         sub = [value] 
        last = value 
   
       #after the loop we send the final subsequence 
       yield sub 
   

   두 음 :

   하나의 구현 발전기를 사용하여이 될 수있다 next(seq)에서 제외 시키십시오 - 그러나 from __future__ import generator_stop이 일 때 RuntimeError이 앞으로 호환되도록해야합니다. 필요하지 않습니다. o 그것을 잡아서 명시 적으로 return.

2. 빈 목록을 all_ascending_subsequences에 전달하면 아무 값도 생성되지 않으므로 이 원하는 동작이 될 수 있습니다. 빈 목록이 전달되면 yield []에서 까지 빈 목록을 생성하십시오.

그런 다음 당신은이 꽤 사소한 알고리즘이 많다는 것 key=len

b = [1,2,3,4,1,5,1,6,7] 

result = max(all_ascending_subsequences(b),key=len) 
print("longest is", result) 

#print(*all_ascending_subsequences(b))