problem.txt (1512B)
1 Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes ai money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence ai. 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. 2 3 Help Kefa cope with this task! 4 Input 5 6 The first line contains integer n (1 ≤ n ≤ 105). 7 8 The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109). 9 Output 10 11 Print a single integer — the length of the maximum non-decreasing subsegment of sequence a. 12 13 --- 14 15 - n days 16 - ith day he makes a_i money 17 - max non-decreasing subsegment in sequence a_i 18 - continuous fragment of a_i 19 - all numbers follow a non-decreasing order 20 - so fragment that's strictly increasing 21 22 --- 23 24 2 2 1 3 4 1 25 26 2,2 27 28 1,3,4 29 30 3,4 31 32 best = 3 33 34 length is returned, not sum 35 36 --- 37 38 2 2 9 39 40 2 , 2 , 9 41 42 length = 3 43 44 --- 45 46 - idea: 47 - the best length from the current idx onwards is the best length of the next + current iff next is part of the longest 48 - recursively defined as: 49 - longest(idx) = let pair = longest(idx) if pair.inc then if ls[idx] <= ls[idx+1] then pair.val + 1 else max(1,pair.val) else max(1,pair.val) 50 - either we return the next 51 - base case is going beyond arr bounds