मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें एक या शून्य तत्वों को हटाकर प्राप्त की जा सकने वाली सख्ती से बढ़ती सन्निकट सबलिस्ट की अधिकतम लंबाई ढूंढनी है।
उदाहरण के लिए, यदि इनपुट nums = [30, 11, 12, 13, 14, 15, 18, 17, 32] है, तो आउटपुट 7 होगा, क्योंकि जब हम सूची में 18 को हटाते हैं तो हमें [11, 12, 13, 14, 15, 17, 32] मिलता है जो सबसे लंबी, सन्निकट, सख्ती से बढ़ती सबलिस्ट है, और इसकी लंबाई 7 है।
इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:
- n := nums का आकार
- pre := आकार n की सूची, 1 से भरी हुई
- i को 1 से n-1 तक के लिए करें:
- यदि nums[i] > nums[i-1], तो pre[i] := pre[i-1] + 1
- suff := आकार n की सूची, 1 से भरी हुई
- i को n-2 से -1 तक घटाते हुए करें:
- यदि nums[i] < nums[i+1], तो suff[i] := suff[i+1] + 1
- ans := max(pre का अधिकतम, suff का अधिकतम)
- i को 1 से n-1 तक के लिए करें:
- यदि nums[i-1] < nums[i+1], तो ans := max(ans, pre[i-1] + suff[i+1])
- ans वापस करें
उदाहरण
class Solution:
def solve(self, nums):
n = len(nums)
pre = [1] * n
for i in range(1, n):
if nums[i] > nums[i-1]:
pre[i] = pre[i-1] + 1
suff = [1] * n
for i in range(n-2, -1, -1):
if nums[i] < nums[i+1]:
suff[i] = suff[i+1] + 1
ans = max(max(pre), max(suff))
for i in range(1, n-1):
if nums[i-1] < nums[i+1]:
ans = max(ans, pre[i-1] + suff[i+1])
return ans
ob = Solution()
nums = [30, 11, 12, 13, 14, 15, 18, 17, 32]
print(ob.solve(nums))
इनपुट
[30, 11, 12, 13, 14, 15, 18, 17, 32]
आउटपुट
7