algorithms

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

commit ddeef28235e8f97ea57a88d984ff83a9bb34402a
parent 2b132a8cb6f57031563cb5c021ffa29763013bd8
Author: Andrew Laack <andrew@laack.co>
Date:   Tue, 10 Nov 2026 17:36:35 -0600

Easy problem in ocaml

Diffstat:
Acomp/prefix-max/ex1.in | 9+++++++++
Acomp/prefix-max/main.ml | 30++++++++++++++++++++++++++++++
Acomp/prefix-max/problem.txt | 17+++++++++++++++++
3 files changed, 56 insertions(+), 0 deletions(-)

diff --git a/comp/prefix-max/ex1.in b/comp/prefix-max/ex1.in @@ -0,0 +1,9 @@ +4 +5 +2 1 4 5 3 +2 +5 1 +3 +3 2 1 +2 +6 7 diff --git a/comp/prefix-max/main.ml b/comp/prefix-max/main.ml @@ -0,0 +1,30 @@ +let read_int () = + Scanf.scanf " %d" (fun x -> x) + in + +let rec readInts size = + if size <> 0 then read_int () :: readInts (size - 1) + else [] +in + +let largest arr = + let rec acc best arr = + match arr with + | h :: t -> acc (if h > best then h else best) t + | [] -> best + in + match arr with + | [] -> failwith "Empty list" + | h :: t -> acc h t +in + +let rec handleTestCase num = + let size = read_int() in + let arr = readInts size in + let largest = largest arr in + let () = print_int (largest * size) in + let () = print_newline () in + if num > 1 then (handleTestCase (num - 1)) else () +in + +handleTestCase (read_int ()) diff --git a/comp/prefix-max/problem.txt b/comp/prefix-max/problem.txt @@ -0,0 +1,17 @@ +You are given an array of n integers a1,a2,…,an. + +The value of an array is the sum of the maximums of each prefix of the array. More formally, the value of an array a is ∑ni=1max(a1,…,ai). For example, the value of the array [1,2,1] is max(1)+max(1,2)+max(1,2,1)=1+2+2=5. + +You can choose two indices i and j and swap elements ai and aj; this operation can be applied at most one time. + +Find the maximum possible value of the array a after at most one operation. + +--- + +so basically we have the following: + - an array where we can reorder two elements to make max(a_1,...) + max(a_1,...) ... where we are only summing the first n elements per step + - in this case we want to find the largest element of the array and swap it with the front element + - we then know the max across each of the n arrays is the largest element so the total sum is simply n*maxNum + +--- +