Cho dãy số gồm N phần tử A1, A2, ..., AN (1 <= n <= 10^6). Hãy tìm một đoạn con liên tiếp dài nhất các phần tử đan dấu nhau. Input: Dòng đầu tiên nhập số N Dòng tiếp theo nhập các số A1, A2, , AN Output: Một số duy nhất là độ dài đoạn con đan dấu liên tiếp dài nhất c++

Thuật toán: Dạng bài tìm đoạn con này ta sử dùng thuật toán Quy hoạch động.

$\\$

$\texttt{C++}$

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> a(n);
    vector<int> d(n,1);
    for(int&i:a) cin>>i;
    for(int i=1;i<n;i++)
    {
        if(a[i]*a[i-1]<0) d[i]=d[i-1]+1;
    }
    cout<<*max_element(d.begin(),d.end());
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,dem=1,res=1;
int main()
{
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        if((a[i]>0&&a[i-1]>0)||(a[i]<0&&a[i-1]<0)) {
            dem++;
            res=max(res,dem);
        } else {
            dem=1;
        }
    }
    cout<<res;
}