Link Sub: http://www.spoj.com/PTIT/problems/BCINCSEQ/
Người Gửi: Dương Lee
- Problem:
Cho dãy số nguyên A = (a1, a2, …, an). Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy A có thứ tự không giảm
Quy ước: Đoạn chỉ gồm đúng 1 phần tử trong A cũng được coi là có thứ tự không giảm
Input
Dòng 1 chứa số nguyên dương n ≤ 105
Dòng 2 chứa n số nguyên a1, a2, ..., an ("i: |ai| ≤ 109) cách nhau ít nhất một dấu cách
Output
Một số nguyên duy nhất là số phần tử trong đoạn tìm được
Example:
Một số nguyên duy nhất là số phần tử trong đoạn tìm được
Input
11
88 99 11 22 22 33 11 66 33 44 77
Output:
4
- Solution:
Vì dãy tăng liên tiếp nên ta có dãy arr2[] (chiều dài max) quy hoạch sau:Với i:= 1->n-1; arr2[0]=1;
- arr1[i]>=arr[i-1] thì arr2[i] = arr2[i-1]+1;
- arr1[i]< arr[i-1] thì arr2[i] = 1;
Với test mẫu trên ta thu được:
arr2[i:=0->n-1] = {1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 3};
Có nghĩa là arr2[i] lưu lại số lượng phần tử tại đó mà dãy đang tăng. Sau đó tìm max (arr2[i:=0->n-1])
- Code:
C++:
https://ideone.com/qfIljk
#include <iostream>
using namespace std;
int main ()
{
int n;
cin>>n;
long arr[100005];
for (int i=0; i<n; i++)
{
cin>>arr[i];
}
int arr2[100005];
arr2[0] = 1;
for (int i=1; i<n; i++)
{
if (arr[i]>=arr[i-1])
arr2[i] = arr2[i-1]+1;
else
arr2[i]=1;
}
int Dmax = 0;
for (int i=0; i<n; i++)
{
if (arr2[i]>Dmax) Dmax = arr2[i];
}
cout<<Dmax;
return 0;
}