Python에서 가장 긴 증가 부분 수열

<시간/>

정렬되지 않은 정수 목록이 있다고 가정합니다. 가장 긴 증가 부분 수열을 찾아야 합니다. 따라서 입력이 [10,9,2,5,3,7,101,18]이면 증가하는 부분 시퀀스가 [2,3,7,101]

이므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

trail :=길이가 0에서 nums의 길이가 1인 배열, 0으로 채움
크기 :=0
숫자 단위의 x에 대해
- i :=0, j :=크기
- 내가 j가 아닌 동안
  - 중간:=i + (j - i) / 2
  - trails[mid]
- 궤적[i] :=x
- 크기 :=i + 1 및 크기의 최대값
반환 크기

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution(object):
   def lengthOfLIS(self, nums):
      tails =[0 for i in range(len(nums))]
      size = 0
      for x in nums:
         i=0
         j=size
         while i!=j:
            mid = i + (j-i)//2
            if tails[mid]< x:
               i= mid+1
            else:
               j = mid
               tails[i] = x
               size = max(i+1,size)
               #print(tails)
      return size
ob1 = Solution()
print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))

입력

[10,9,2,5,3,7,101,18]