मान लीजिए हमारे पास संख्याओं का एक अनुक्रम है जिसे विगल अनुक्रम कहा जाता है यदि क्रमिक संख्याओं के बीच का अंतर सख्ती से धनात्मक और ऋणात्मक के बीच बारी-बारी से होता है। पहला अंतर या तो धनात्मक या ऋणात्मक हो सकता है। दो से कम तत्वों वाला अनुक्रम तुच्छ रूप से एक विगल अनुक्रम है।
उदाहरण के लिए, [1,7,4,9,2,5] एक विगल अनुक्रम है क्योंकि यदि आप देखें, तो अंतर (6,-3,5,-7,3) बारी-बारी से धनात्मक और ऋणात्मक हैं। लेकिन, [1,4,7,2,5] और [1,7,4,5,5] विगल अनुक्रम नहीं हैं, पहला क्योंकि इसके पहले दो अंतर धनात्मक हैं और दूसरा क्योंकि इसका अंतिम अंतर शून्य है।
इसलिए हमारे पास पूर्णांकों का एक अनुक्रम है, हमें सबसे लंबे उपअनुक्रम की लंबाई ढूंढनी है जो एक विगल अनुक्रम है। एक उपअनुक्रम मूल अनुक्रम से कुछ तत्वों को हटाकर (अंततः, शून्य भी) प्राप्त किया जाता है, शेष तत्वों को उनके मूल क्रम में छोड़कर।
उदाहरण के लिए, यदि इनपुट [1,7,4,9,2,5] जैसा है, तो आउटपुट 6 होगा। क्योंकि पूरा अनुक्रम एक विगल अनुक्रम है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
n := nums का आकार- यदि
n = 0, तो 0 लौटाएं up := 1औरdown := 1सेट करेंiको 1 सेn - 1तक लूप करें- यदि
nums[i] > nums[i - 1], तोup := down + 1 - अन्यथा जब
nums[i] < nums[i - 1], तोdown := up + 1
- यदि
up और down का अधिकतमलौटाएं
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); if(!n) return 0; int up = 1; int down = 1; for(int i = 1; i < n; i++){ if(nums[i] > nums[i - 1]){ up = down + 1; } else if(nums[i] < nums[i - 1]){ down = up + 1; } } return max(up, down); } }; main(){ Solution ob; vector<int> v = {1,7,4,9,2,5}; cout << (ob.wiggleMaxLength(v)); }इनपुट
[1,7,4,9,2,5]
आउटपुट
6
