algorithms

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

commit 0b233bc54ea3faeaa6271ad4a26bbe974dc363ef
parent 1d50d7c09fe35fe9d180964ae78a8a634a69bd01
Author: Andrew Laack <andrew@laack.co>
Date:   Wed, 11 Nov 2026 17:33:26 -0600

Precomputation with ocaml

Diffstat:
Acomp/kefa-and-first-steps/ex1.in | 2++
Acomp/kefa-and-first-steps/ex2.in | 2++
Acomp/kefa-and-first-steps/main.ml | 28++++++++++++++++++++++++++++
Acomp/kefa-and-first-steps/problem.txt | 51+++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 83 insertions(+), 0 deletions(-)

diff --git a/comp/kefa-and-first-steps/ex1.in b/comp/kefa-and-first-steps/ex1.in @@ -0,0 +1,2 @@ +6 +2 2 1 3 4 1 diff --git a/comp/kefa-and-first-steps/ex2.in b/comp/kefa-and-first-steps/ex2.in @@ -0,0 +1,2 @@ +3 +2 2 9 diff --git a/comp/kefa-and-first-steps/main.ml b/comp/kefa-and-first-steps/main.ml @@ -0,0 +1,28 @@ +let readNext () = Scanf.scanf " %d" (fun x -> x) in +let rec scanAll idx arr = + if idx >= Array.length arr then () + else + let next = readNext () in + Array.set arr idx next; + scanAll (idx + 1) arr +in +let solve arr = + let soln = Array.make (Array.length arr) 0 in + let rec acc idx = + if idx = Array.length arr then 0 + else + let best = acc (idx + 1) in + if idx < Array.length arr - 1 && arr.(idx) <= arr.(idx + 1) then + let () = soln.(idx) <- soln.(idx + 1) + 1 in + max soln.(idx) best + else + let () = soln.(idx) <- 1 in + max 1 best + in + acc 0 +in +let numbers = readNext () in +let arr = Array.make numbers 0 in +let () = scanAll 0 arr in +print_int (solve arr); +print_newline () diff --git a/comp/kefa-and-first-steps/problem.txt b/comp/kefa-and-first-steps/problem.txt @@ -0,0 +1,51 @@ +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. + +Help Kefa cope with this task! +Input + +The first line contains integer n (1 ≤ n ≤ 105). + +The second line contains n integers a1,  a2,  ...,  an (1 ≤ ai ≤ 109). +Output + +Print a single integer — the length of the maximum non-decreasing subsegment of sequence a. + +--- + +- n days +- ith day he makes a_i money +- max non-decreasing subsegment in sequence a_i + - continuous fragment of a_i + - all numbers follow a non-decreasing order + - so fragment that's strictly increasing + +--- + +2 2 1 3 4 1 + +2,2 + +1,3,4 + +3,4 + +best = 3 + +length is returned, not sum + +--- + +2 2 9 + +2 , 2 , 9 + +length = 3 + +--- + +- idea: + - the best length from the current idx onwards is the best length of the next + current iff next is part of the longest + - recursively defined as: + - 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) + - either we return the next + - base case is going beyond arr bounds