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

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

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

در مورد سایت کوئرا بیشتر بخوانید…

تمرین جدی کوئرا + سی پلاس پلاس

بابای حسنی به حسنی سوالی را داده و به او گفته تا این سوال را حل کند. اما چون حسنی زیاد علاقه‌ای به حل سوال ندارد، از شما خواسته تا این سوال را برای او حل کنید.

آرایه‌ای به نام $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;
        
}

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

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

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

موفق باشید.