Author: SQU_Test
DIFFICULTY:
Easy
PREREQUISITES:
Dynamic Programming, count.
PROBLEM:
Amal decided to make some money doing business on the Internet for exactly n days. She knows that on the i-th day (1 ≤ i ≤ n) she makes a_i money. Amal loves progress, that’s why she wants to know the length of the maximum non-decreasing subsegment in sequence a_i. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.
Help Amal cope with this task!
EXPLANATION:
Note, that if the array has two intersecting continuous non-decreasing subsequence, they can be combined into one. Therefore, you can just pass the array from left to right. If the current subsequence can be continued using the i-th element, then we do it, otherwise we start a new one. The answer is the maximum subsequence of all the found ones.
TIME COMPLEXITY:
Time complexity of the solution is O(n).
SOLUTIONS:
Setter’s Solution
#include <cstdio>
using namespace std;
int main(){
int n;
scanf("%d", &n);
int a[n];
for(int i=0;i <n;i++){
scanf("%d", &a[i]);
}
int count = 1, max_count = 1;
for(int i=1; i<n; i++){
if (a[i] >= a[i-1]){
count ++;
if (count > max_count) max_count = count;
}
else count = 1;
}
printf("%d", max_count);
}