मान लीजिए हमारे पास nums नाम की संख्याओं की एक सूची है, हमें सबसे लंबे बढ़ते सबसीक्वेंस की लंबाई ढूंढनी है और हम मान रहे हैं कि सबसीक्वेंस सूची की शुरुआत में वापस लपेट सकता है।
इसलिए, यदि इनपुट इस तरह है nums = [6, 5, 8, 2, 3, 4], तो आउटपुट 5 होगा, क्योंकि सबसे लंबा बढ़ता सबसीक्वेंस [2, 3, 4, 6, 8] है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- a := nums के आकार से दोगुनी आकार की सूची बनाएं और nums को दो बार भरें
- ans := 0
- i के लिए 0 से nums के आकार तक रेंज में, करें
- dp := एक नई सूची
- j के लिए i से nums के आकार + i - 1 तक रेंज में, करें
- n := a[j]
- k := n को dp में डालने के लिए बायां सबसे इंडेक्स
- यदि k, dp के आकार के समान है, तो
- n को dp के अंत में डालें
- अन्यथा,
- dp[k] := n
- ans := ans और dp के आकार का अधिकतम
- ans लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
import bisect
class Solution:
def solve(self, nums):
a = nums + nums
ans = 0
for i in range(len(nums)):
dp = []
for j in range(i, len(nums) + i):
n = a[j]
k = bisect.bisect_left(dp, n)
if k == len(dp):
dp.append(n)
else:
dp[k] = n
ans = max(ans, len(dp))
return ans
ob = Solution()
nums = [4, 5, 8, 2, 3, 4]
print(ob.solve(nums))इनपुट
[4, 5, 8, 2, 3, 4]
आउटपुट
5