پاسخ سوال جدی کوئرا

پاسخ سوال جدی کوئرا

در این نوشته تمرین “جدی” که در وب‌سایت کوئرا موجود است را برای شما کاربران عزیز حل کرده‌ایم.

پاسخ سوال جدی کوئرا

بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید. آرایه‌ای به نام $a$ به طول $n$ داریم. می‌خواهیم بلندترین زیردنباله‌ای از آرایه را پیدا کنیم که صعودی نزولی شود. حسنی به دنباله b0​,b1​,...,bk−1 ​ صعودی-نزولی می‌گوید اگر سه شرط زیر برای آن برقرار شود:

• به ازای برای هر i فرد که $0<i<k-1$ داشت: bi−1​<bi​>bi+1​ 
• به ازای برای هر i زوج که $0<i<k-1$ داشت: bi−1​>bi​<bi+1​ 
• برای $i$ برابر با صفر می‌توان گقت: 0​<b1​

حال شما باید طول بلندترین زیردنباله‌ای از آرایه $a$ که صعودی-نزولی است را پیدا کنید و آن را چاپ کنید.

نکته: به آرایه $b$ یک زیردنباله از آرایه $a$ می‌گوییم اگر بتوان با حذف تعدادی عضو از آرایه a به آرایه b رسید.

ورودی سوال جدی

در اولین خط ورودی عدد $n$ و در خط بعدی n عدد امده است که عدد $i$ ام مقدار خانه $i$ ام آرایه است.

$$1\; \le n\le 100000$$

∣ai​∣ ≤ 10^9

خروجی سوال جدی

در تنها خط خروجی طول بلندترین زیردنباله صعودی-نزولی را بگویید.

حل سوال جدی

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<int> don;
    don.resize(n);
    for(int i=0; i<n; i++)
        cin >> don[i];
        
 
    bool soodi = false;
    bool nozoli = true;
    int tol = 1;
    for(int j=0; j<n-1; j++)
    {
        if(don[j] < don[j+1])
        {
            if(soodi)
            {
                continue;
            }
            else
            {
                soodi = true;
                nozoli = false;
                tol ++;
            }
            
        }
        else
        {
            if(nozoli)
            {
                continue;
            }
            else
            {
                soodi = false;
                nozoli = true;
                tol ++;
            }
        }
    }
    
 
    cout << tol;
        
}

منبع سوال‌: وبسایت کوئرا

اگر روش حل بهتری برای “تمرین جدی” دارید برای ما ارسال کنید تا با نام خودتان به اشتراک بگذاریم. اگر سوال خاصی را مدنظر دارید در بخش نظرات برای ما ارسال کنید تا حل آن سوال را در الویت محتوای سایت بگذاریم.