C++-এ উইগল সাবসিকোয়েন্স

একটি সংখ্যা সিকোয়েন্সকে উইগল সিকোয়েন্স বলা হয় যদি অনুক্রমিক সংখ্যাগুলোর পার্থক্য কঠোরভাবে পজিটিভ ও নেগেটিভে অল্টারনেট করে। প্রথম পার্থক্য পজিটিভ বা নেগেটিভ যেকোনো হতে পারে। দুটি কম উপাদান থাকলে সেটি স্বয়ংক্রিয়ভাবে উইগল সিকোয়েন্স। উদাহরণ: [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] হলে আউটপুট ৬, কারণ পুরো সিকোয়েন্সই উইগল।

সমাধানের ধাপগুলো:

• n := nums.size()
• যদি n == 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
• max(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