ลำดับการกระดิกใน 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] เอาต์พุตจะเป็น 6 เนื่องจากลำดับทั้งหมดเป็นลำดับการกระดิก

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums

• ถ้า n เป็น 0 ให้คืนค่า 0

• ตั้งค่า :=1 และลง :=1

• สำหรับผมอยู่ในช่วง 1 ถึง n – 1

  • ถ้า nums[i]> nums[i – 1] แล้ว up :=down + 1

  • มิฉะนั้นเมื่อ nums[i]

• ผลตอบแทนสูงสุดของขึ้นและลง

ตัวอย่าง (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