최대 단조 증가 또는 감소 서브 시퀀스

아래는 최대 모노톤 서브 시퀀스 (증가 또는 감소)에 대한 내 코드입니다. 나는 이것을 코딩하기 전에 어떤 연구도하지 않았으며 일반적인 컴퓨터 과학 문제라는 것을 모르고있었습니다. 후속 연구에서, 일반적으로 받아 들여지는 가장 효율적인 알고리즘은 O (N log N) 인 것으로 보인다. 이것들은 일반적으로 동적 인 프로그래밍 방식의 솔루션으로, 현 시점에서 약간 머리가 맞습니다.최대 단조 증가 또는 감소 서브 시퀀스

알고리즘 전문가가 아니지만 다음 코드는 O (N)가 아닙니다. 나는 각 목록을 두 번지나 가며 한 번씩 증가하는 서열을 찾는다.

나는 또한 그것을 정리하는 조언을 주셔서 감사하겠습니다. 나는 함수가 매우 중복 적이라는 것을 알았지 만, 두 번째 기능/반복의 반복없이 모든 것을 수행하는 좋은 방법을 찾지 못했습니다.

def largest_monotonic_subsequence(lst): 

    def increasing(lst): 
     beg,end,best = 0,0,[0,0] 
     for i in range(len(lst)-1): 
      if lst[i] <= lst[i+1]: 
       end = i+1 
       if end - beg > best[1] - best[0]: 
        best = beg, end 
      else: 
       beg = i+1 
     return (best[0],best[1]+1) 

    def decreasing(lst): 
     beg,end,best = 0,0,[0,0] 
     for i in range(len(lst)-1): 
      if lst[i] >= lst[i+1]: 
       end = i+1 
       if end - beg > best[1] - best[0]: 
        best = beg, end 
      else: 
       beg = i+1 
     return (best[0],best[1]+1) 

    incr = increasing(lst) 
    decr = decreasing(lst) 
    return lst[slice(*max([incr,decr], key = lambda x: x[1]-x[0]))]

출처

2016-10-31 Solaxun

비교의 의미를 반대로 +1 또는 -1로 설정 부호 인수를 사용할 수 있습니다 " –

[수학] (https://en.wikipedia.org/wiki/Subsequence)에서 하위 시퀀스는 나머지 요소의 순서를 변경하지 않고 일부 요소를 삭제하여 다른 시퀀스에서 파생 될 수있는 시퀀스입니다. [...] 하위 문자열을 하위 문자열과 혼동해서는 안됩니다. –

죄송합니다. 그래서이 질문은 MIT OCW 수업의 일환으로 제가 도와주었습니다. 문제를 해결 한 후 "단조롭게 시험을 증가"하고 뚜렷하게 RTFM을하지 않았습니다. 연속적인 것이 기준이 아니면 왜 이것이 더 어려운 문제인지 분명히 알 수 있습니다. 바보 같은 질문에 사과. – Solaxun

당신은 *이 서브 반드시 연속 *, 또는 고유하지 않습니다 ", 위키 피 디아에서

if sgn * lst[i] <= sgn * lst[i+1]:

출처

2016-10-31 14:25:50 f5r5e5d

최대 단조 증가 또는 감소 서브 시퀀스

답변

관련 문제