पायथन में एक तत्व हटाने के बाद सख्ती से बढ़ते हुए सबसे लंबे सन्निहित सबलिस्ट की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें सन्निहित सख्ती से बढ़ते हुए सबलिस्ट की अधिकतम लंबाई ढूंढनी है। हमें सूची से अधिकतम एक तत्व हटाने की अनुमति है।

उदाहरण के लिए, यदि इनपुट है nums = [35, 5, 6, 7, 8, 9, 12, 11, 26], तो आउटपुट 7 होगा, क्योंकि यदि हम nums से 12 हटाते हैं, तो सूची [5, 6, 7, 8, 9, 11, 26] बन जाएगी, जिसकी लंबाई 7 है, यह सबसे लंबा, सन्निहित, सख्ती से बढ़ता हुआ सबलिस्ट है।

एल्गोरिदम

यदि nums खाली है, तो 0 लौटाएं
end := nums के आकार की सूची, 1 से भरी हुई
start := nums के आकार की सूची, 1 से भरी हुई
बाएं से दाएं: end[i] की गणना करें जो i पर समाप्त होने वाले सबसे लंबे बढ़ते सबलिस्ट की लंबाई है
दाएं से बाएं: start[j] की गणना करें जो j से शुरू होने वाले सबसे लंबे बढ़ते सबलिस्ट की लंबाई है
res := end और start के तत्वों का अधिकतम
प्रत्येक k के लिए 1 से len(nums)-2 तक:
- यदि nums[k-1] < nums[k+1], तो res = max(res, end[k-1] + start[k+1])
res लौटाएं

उदाहरण कार्यान्वयन

def solve(nums):
    if not nums:
        return 0
    end = [1 for i in nums]
    start = [1 for i in nums]
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            end[i] = end[i-1] + 1
    for j in range(len(nums)-2, -1, -1):
        if nums[j+1] > nums[j]:
            start[j] = start[j+1] + 1
    res = max(max(end), max(start))
    for k in range(1, len(nums)-1):
        if nums[k-1] < nums[k+1]:
            res = max(res, end[k-1] + start[k+1])
    return res

nums = [35, 5, 6, 7, 8, 9, 12, 11, 26]
print(solve(nums))  # आउटपुट: 7

इनपुट

[35, 5, 6, 7, 8, 9, 12, 11, 26]