Python에서 가장 길게 증가하는 부분 수열의 길이를 찾는 프로그램

<시간/>

숫자 목록이 있다고 가정합니다. 가장 긴 증가하는 수열의 길이를 찾아야 합니다. 따라서 입력이 [6, 1, 7, 2, 8, 3, 4, 5]와 같으면 가장 긴 증가 부분 시퀀스가 [2,3,4,5,6]이므로 출력은 5가 됩니다.

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

nums와 크기가 같은 tails라는 배열을 만들고 0으로 채웁니다.
크기 :=0
nums 배열의 각 요소 x에 대해 -
- i :=0, j :=크기
- i가 j와 같지 않은 동안
  - 중간 :=i + (j – i)/2
  - tails[mid]
- 꼬리[i] :=x
- 크기 :=최대 i + 1 및 크기
크기를 반환합니다.

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

예

class Solution(object):
   def solve(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)
      return size

ob = Solution()
nums = [7, 2, 8, 3, 9, 4, 5, 6]
print(ob.solve(nums))

입력

[7, 2, 8, 3, 9, 4, 5, 6]