पायथन में सबसे लंबा बढ़ता हुआ सबसीक्वेंस

मान लीजिए हमारे पास पूर्णांकों की एक अनसॉर्टेड लिस्ट है। हमें सबसे लंबा बढ़ता हुआ सबसीक्वेंस ढूंढना है। इसलिए यदि इनपुट [10,9,2,5,3,7,101,18] है, तो आउटपुट 4 होगा, क्योंकि बढ़ता हुआ सबसीक्वेंस [2,3,7,101] है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• trail := लंबाई 0 से nums की लंबाई - 1 तक का एक ऐरे, और इसे 0 से भरें
• size := 0
• nums में प्रत्येक x के लिए
  • i := 0, j := size
  • जब तक i, j के बराबर नहीं है
    • mid := i + (j - i) / 2
    • यदि trails[mid] < x, तो i := mid + 1, अन्यथा j := mid
  • trails[i] := x
  • size := i + 1 और size का अधिकतम
• size लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें -

उदाहरण

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)
        return size

ob1 = Solution()
print(ob1.lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))

इनपुट

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

आउटपुट

4