पायथन में सबसे लंबी बढ़ती हुई उप-अनुक्रम की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास संख्याओं की एक सूची है। हमें सबसे लंबी बढ़ती हुई उप-अनुक्रम (Longest Increasing Subsequence) की लंबाई ढूंढनी है। उदाहरण के लिए, यदि इनपुट [6, 1, 7, 2, 8, 3, 4, 5] है, तो आउटपुट 5 होगा, क्योंकि सबसे लंबी बढ़ती हुई उप-अनुक्रम [2, 3, 4, 5, 6] है।

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

• tails नामक एक सरणी बनाएं जिसका आकार nums के बराबर हो, और इसे 0 से भरें।

• size := 0 आरंभ करें।

• nums सरणी के प्रत्येक तत्व x के लिए:

  • i := 0, j := size सेट करें।

  • जब तक i != j हो:

    • mid := i + (j - i) // 2 की गणना करें।

    • यदि tails[mid] < x, तो i := mid + 1, अन्यथा j := mid।

  • tails[i] := x असाइन करें।

  • size := max(i + 1, size) अपडेट करें।

• size लौटाएं।

उदाहरण

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]

आउटपुट

5