카운터 예를

사람이 정수의 순서에서 가장 긴 증가 서브 찾으려면 다음 알고리즘 뭐가 잘못 말해 수 :카운터 예를

def longest_increasing_subsequence(sequence): 
    """ 

    Examples: 

    >>> longest_increasing_subsequence([]) 
    [] 
    >>> longest_increasing_subsequence([1]) 
    [1] 
    >>> longest_increasing_subsequence([1, 2]) 
    [1, 2] 
    >>> longest_increasing_subsequence([2, 1]) 
    [1] 
    >>> longest_increasing_subsequence([1, 2, 3]) 
    [1, 2, 3] 
    >>> longest_increasing_subsequence([3, 1, 2]) 
    [1, 2] 
    >>> longest_increasing_subsequence([5, 1, 3, 2, 6]) 
    [1, 2, 6] 
    >>> longest_increasing_subsequence([1, 6, 3, 5, 9, 7]) 
    [1, 3, 5, 7] 
    >>> longest_increasing_subsequence([3, 1, 2, 4, 6]) 
    [1, 2, 4, 6] 
    >>> longest_increasing_subsequence([0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]) 
    [0, 4, 6, 9, 11, 15] 
    >>> longest_increasing_subsequence([1, 10, 2, 9, 3, 8, 4, 7, 5, 6]) 
    [1, 2, 3, 4, 5, 6] 

    """ 
    if not sequence: 
     return [] 

    result = [sequence[0]] 
    for i in sequence[1:]: 
     if i < result[0]: 
      result = [i] 
     elif i > result[-1]: 
      result.append(i) 
     elif len(result) >= 2 and i > result[-2]: 
       result[-1] = i 

    return result

것은 당신이 반대를 찾을 수 있습니까를 예를 들어 잘못된 결과를 반환합니까?

출처

2014-06-10 Greg Leclercq

이 알고리즘은 잘못된 알고리즘 구현을 입증 할 수있는 데이터 집합을 식별하는 데 도움이되지 않기 때문에 주제가 아닌 것 같습니다. 시험 스위트가 필요한가요? –

'[1,10,2,20,30,3,4,5]'와'[2,3,1]' – M4rtini

감사합니다. 나는 그 검사가 철저하지 않고 틀린 가정을했다고 동의한다. '[2,3,1]은 그것을 분명하게 보여준다. –

논리의 문제점은 가장 길게 증가하는 하위 시퀀스가 가장 낮은 숫자로 시작한다고 가정한다는 것입니다. 이는 다음과 같은 오류입니다.

>>> longest_increasing_subsequence([2, 3, 4, 5, 6, 1]) 
[1]

출처

2014-06-10 15:03:25 cchristelis

카운터 예를

답변

관련 문제