algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

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