import Mathlib /-! # Split Array Largest Sum Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split. A subarray is a contiguous part of the array. ## Constraints - 1 <= nums.length <= 1000 - 0 <= nums[i] <= 10^6 - 1 <= k <= min(50, nums.length) ## Provided examples - `nums = [7, 2, 5, 10, 8], k = 2` → `18` - `nums = [1, 2, 3, 4, 5], k = 2` → `9` - `nums = [1, 4, 4], k = 3` → `4` ## Synthesized negative examples - invalid input: `nums = [-1], k = 1` ([structural] a predicate that admits 0 <= nums[i] <= 10^6. negative number under the non-negative bound) - invalid input: `nums = [1000001], k = 1` ([structural] a predicate that admits 0 <= nums[i] <= 10^6. one over the stated maximum) - invalid input: `nums = [1, 2, 3], k = 4` ([structural] a predicate that admits 1 <= k <= min(50, nums.length). k exceeds nums.length; each argument alone is legal) - `nums = [7, 2, 5, 10, 8], k = 2` → `23` is wrong ([structural] minimality stated as achievability alone. 23 is max of [7,2] and [5,10,8], but not least) - `nums = [1, 2, 3, 4, 5], k = 2` → `12` is wrong ([structural] minimality stated as achievability alone. Split [1,2] and [3,4,5] has largest sum 12, but 9 is smaller.) - `nums = [1, 4, 4], k = 3` → `9` is wrong ([structural] k is not required to be the number of subarrays. 9 uses one subarray, so the input's k is ignored.) -/ namespace PSplitArrayLargestSum abbrev Input := (List Int) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- `blocks` splits `nums` into exactly `k` non-empty contiguous subarrays. -/ def IsValidSplit (nums : List Int) (k : Nat) (blocks : List (List Int)) : Prop := blocks.flatten = nums ∧ blocks.length = k ∧ ∀ b ∈ blocks, b ≠ [] /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ nums.length ≤ 1000`, every element in `[0, 10^6]`, and `1 ≤ k ≤ 50` with `k ≤ nums.length`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 1000 && input.1.all (fun x => 0 ≤ x && x ≤ 1000000) && 1 ≤ input.2 && input.2 ≤ 50 && input.2 ≤ input.1.length /-! ### Ideal specification (P_spec) -/ /-- `result` is the least largest block sum attained by any valid split of `input.1` into `input.2` blocks: some split attains it, and no split goes below. -/ def splitArrayLargestSum_spec (input : Input) (result : Output) : Prop := IsLeast {m : Int | ∃ blocks : List (List Int), IsValidSplit input.1 input.2 blocks ∧ IsGreatest {s : Int | ∃ b ∈ blocks, b.sum = s} m} (result : Int) /-! ### Decidable specification (P_check) -/ /-- One Bool per gap between adjacent elements of `nums`: a choice of cut points. -/ abbrev CutCode (nums : List Int) : Type := Fin (nums.length - 1) → Bool /-- Adjacent pairs of a list, `[a, b, c] ↦ [(a, b), (b, c)]`. -/ def consecutivePairs : List Nat → List (Nat × Nat) | a :: b :: xs => (a, b) :: consecutivePairs (b :: xs) | _ => [] /-- The block boundaries selected by `code`, including both endpoints. -/ def cutPositions (nums : List Int) (code : CutCode nums) : List Nat := 0 :: ((List.finRange (nums.length - 1)).filterMap (fun i => if code i then some (i.val + 1) else none)) ++ [nums.length] /-- The split of `nums` into contiguous blocks selected by the cut points `code`. -/ def decodeSplit (nums : List Int) (code : CutCode nums) : List (List Int) := (consecutivePairs (cutPositions nums code)).map (fun (a, b) => (nums.drop a).take (b - a)) /-- The list of block sums of a split. -/ def blockSums (blocks : List (List Int)) : List Int := blocks.map List.sum /-- `m` is the greatest block sum of `blocks`: a block sum itself and at least every block sum. -/ def isGreatestSum (blocks : List (List Int)) (m : Int) : Prop := m ∈ blockSums blocks ∧ ∀ s ∈ blockSums blocks, s ≤ m /-- All boolean vectors of length `n`, enumerating every `CutCode` of an array of length `n + 1`. -/ def allBoolVecs : Nat → List (List Bool) | 0 => [[]] | n + 1 => (allBoolVecs n).map (false :: ·) ++ (allBoolVecs n).map (true :: ·) /-- Boolean test for `IsValidSplit`. -/ def isValidSplitBool (nums : List Int) (k : Nat) (blocks : List (List Int)) : Bool := blocks.flatten == nums && blocks.length == k && blocks.all (fun b => b != []) /-- Boolean test for `isGreatestSum`. -/ def isGreatestSumBool (blocks : List (List Int)) (m : Int) : Bool := (blockSums blocks).contains m && (blockSums blocks).all (fun s => s ≤ m) /-- Executable checker for `splitArrayLargestSum_spec` over the finite `CutCode`. -/ def splitArrayLargestSum_check (input : Input) (result : Output) : Bool := let valid := (allBoolVecs (input.1.length - 1)).filterMap (fun vec => let code : CutCode input.1 := fun i => vec.getD i.val false let blocks := decodeSplit input.1 code if isValidSplitBool input.1 input.2 blocks then some blocks else none) valid.any (fun blocks => isGreatestSumBool blocks (result : Int)) && valid.all (fun blocks => (blockSums blocks).all (fun s => !((blockSums blocks).all (fun t => t ≤ s)) || ((result : Int) ≤ s))) /-! ### Reflection for the boolean twins -/ theorem one_le_length_of_ne_nil {a : List Int} (h : a ≠ []) : 1 ≤ a.length := by cases a with | nil => exact absurd rfl h | cons _ _ => simp theorem isValidSplitBool_iff (nums : List Int) (k : Nat) (blocks : List (List Int)) : isValidSplitBool nums k blocks = true ↔ IsValidSplit nums k blocks := by rw [isValidSplitBool, IsValidSplit] simp [and_assoc] theorem mem_blockSums_iff (blocks : List (List Int)) (m : Int) : m ∈ blockSums blocks ↔ ∃ b ∈ blocks, b.sum = m := by rw [blockSums, List.mem_map] theorem isGreatestSumBool_iff (blocks : List (List Int)) (m : Int) : isGreatestSumBool blocks m = true ↔ IsGreatest {s : Int | ∃ b ∈ blocks, b.sum = s} m := by rw [isGreatestSumBool, Bool.and_eq_true, List.contains_iff_mem, List.all_eq_true, IsGreatest] constructor · rintro ⟨h1, h2⟩ refine ⟨(mem_blockSums_iff blocks m).mp h1, ?_⟩ intro s hs have := h2 s ((mem_blockSums_iff blocks s).mpr hs) simpa using this · rintro ⟨h1, h2⟩ refine ⟨(mem_blockSums_iff blocks m).mpr h1, ?_⟩ intro s hs have := h2 ((mem_blockSums_iff blocks s).mp hs) simpa using this theorem all_max_iff (blocks : List (List Int)) (r : Int) : (∀ s ∈ blockSums blocks, ((!(blockSums blocks).all fun t => decide (t ≤ s)) || decide (r ≤ s)) = true) ↔ ∀ m : Int, IsGreatest {s : Int | ∃ b ∈ blocks, b.sum = s} m → r ≤ m := by constructor · intro hall m hm have h1 : m ∈ blockSums blocks := (mem_blockSums_iff blocks m).mpr hm.1 have h3 : ((blockSums blocks).all fun t => decide (t ≤ m)) = true := by rw [List.all_eq_true] intro t ht have := hm.2 ((mem_blockSums_iff blocks t).mp ht) simpa using this have h2 := hall m h1 rw [h3] at h2 simpa using h2 · intro hlb s hs cases hmax : ((blockSums blocks).all fun t => decide (t ≤ s)) with | false => simp | true => have hg : IsGreatest {x : Int | ∃ b ∈ blocks, b.sum = x} s := by refine ⟨(mem_blockSums_iff blocks s).mp hs, ?_⟩ intro t ht rw [List.all_eq_true] at hmax have := hmax t ((mem_blockSums_iff blocks t).mpr ht) simpa using this simp [hlb s hg] /-! ### Enumeration completeness: every valid split is decoded by some cut code -/ theorem mem_allBoolVecs_iff : ∀ (n : Nat) (l : List Bool), l ∈ allBoolVecs n ↔ l.length = n := by intro n induction n with | zero => intro l simp [allBoolVecs, List.length_eq_zero_iff] | succ n ih => intro l constructor · intro hmem rw [allBoolVecs, List.mem_append] at hmem rcases hmem with hm | hm <;> rw [List.mem_map] at hm <;> obtain ⟨c, hc, rfl⟩ := hm <;> simp [(ih c).mp hc] · intro hlen cases l with | nil => simp at hlen | cons b rest => have hr : rest.length = n := by simpa using hlen rw [allBoolVecs, List.mem_append] cases b · exact Or.inl (List.mem_map.mpr ⟨rest, (ih rest).mpr hr, rfl⟩) · exact Or.inr (List.mem_map.mpr ⟨rest, (ih rest).mpr hr, rfl⟩) theorem filterMap_finRange_val (m : Nat) (g : Nat → Option Nat) : (List.finRange m).filterMap (fun i : Fin m => g i.val) = (List.range m).filterMap g := by rw [← List.map_coe_finRange_eq_range, List.filterMap_map] rfl theorem filterMap_range_eq_filter (m : Nat) (q : Nat → Bool) : (List.range m).filterMap (fun i => if q (i + 1) then some (i + 1) else none) = ((List.range m).map (fun x => x + 1)).filter q := by induction m with | zero => simp | succ n ih => rw [List.range_succ, List.filterMap_append, ih, List.map_append, List.filter_append] cases hq : q (n + 1) <;> simp [hq] theorem filterMap_finRange_boolMem (m : Nat) (S : List Nat) : (List.finRange m).filterMap (fun i : Fin m => if decide (i.val + 1 ∈ S) then some (i.val + 1) else none) = ((List.range m).map (fun x => x + 1)).filter (fun x => decide (x ∈ S)) := by rw [filterMap_finRange_val m (fun j => if decide (j + 1 ∈ S) then some (j + 1) else none), filterMap_range_eq_filter m (fun x => decide (x ∈ S))] theorem filter_mem_cons_of_not_mem (a : Nat) (l L : List Nat) (h : a ∉ L) : L.filter (fun x => decide (x ∈ a :: l)) = L.filter (fun x => decide (x ∈ l)) := by refine List.filter_congr ?_ intro x hx have hxa : x ≠ a := fun hxe => h (hxe ▸ hx) simp [hxa] theorem filter_mem_eq_of_sublist : ∀ {l L : List Nat}, L.Nodup → l.Sublist L → L.filter (fun x => decide (x ∈ l)) = l := by intro l L hnd hs revert hnd induction hs with | slnil => intro _; rfl | cons a hs ih => intro hnd rw [List.nodup_cons] at hnd have hal : a ∉ _ := fun hm => hnd.1 (hs.subset hm) rw [List.filter_cons_of_neg (by simp [hal]), ih hnd.2] | cons_cons a hs ih => intro hnd rw [List.nodup_cons] at hnd rw [List.filter_cons_of_pos (by simp), filter_mem_cons_of_not_mem a _ _ hnd.1, ih hnd.2] theorem sublist_range_of_pairwise_lt (l : List Nat) (n : Nat) (hp : l.Pairwise (· < ·)) (hb : ∀ x ∈ l, x < n) : l.Sublist (List.range n) := List.sublist_of_subperm_of_pairwise (List.subperm_of_subset (hp.imp Nat.ne_of_lt) (fun x hx => List.mem_range.mpr (hb x hx))) hp List.pairwise_lt_range /-- The blocks of `nums` named by an explicit list of boundaries. -/ def decodeAt (nums : List Int) (ps : List Nat) : List (List Int) := (consecutivePairs ps).map (fun (a, b) => (nums.drop a).take (b - a)) theorem decodeAt_cons_cons (nums : List Int) (x y : Nat) (ps : List Nat) : decodeAt nums (x :: y :: ps) = (nums.drop x).take (y - x) :: decodeAt nums (y :: ps) := rfl theorem decodeAt_pair (nums : List Int) (x y : Nat) : decodeAt nums [x, y] = [(nums.drop x).take (y - x)] := rfl /-- The interior boundaries of a block decomposition laid out from offset `acc`. -/ def innerEnds : Nat → List (List Int) → List Nat | _, [] => [] | _, [_] => [] | acc, a :: b :: rest => (acc + a.length) :: innerEnds (acc + a.length) (b :: rest) theorem innerEnds_nil (acc : Nat) : innerEnds acc [] = [] := rfl theorem innerEnds_singleton (acc : Nat) (a : List Int) : innerEnds acc [a] = [] := rfl theorem innerEnds_cons_cons (acc : Nat) (a b : List Int) (rest : List (List Int)) : innerEnds acc (a :: b :: rest) = (acc + a.length) :: innerEnds (acc + a.length) (b :: rest) := rfl theorem decodeAt_innerEnds (nums : List Int) : ∀ (p : List (List Int)) (start : Nat), p ≠ [] → p.flatten = nums.drop start → decodeAt nums (start :: (innerEnds start p ++ [nums.length])) = p := by intro p induction p with | nil => intro start hne _; exact absurd rfl hne | cons a rest ih => intro start _ hflat cases rest with | nil => have ha : a = nums.drop start := by simpa using hflat have hl2 : a.length = nums.length - start := by rw [ha, List.length_drop] rw [innerEnds_singleton, List.nil_append, decodeAt_pair, ← ha, ← hl2, List.take_length] | cons b rest' => have h1 : a ++ (b :: rest').flatten = nums.drop start := by simpa using hflat have hflat' : (b :: rest').flatten = nums.drop (start + a.length) := by have h2 := congrArg (List.drop a.length) h1 rwa [List.drop_left' rfl, List.drop_drop] at h2 have hIH := ih (start + a.length) (by simp) hflat' rw [innerEnds_cons_cons, List.cons_append, decodeAt_cons_cons, hIH] have hsub : start + a.length - start = a.length := by omega rw [hsub, ← h1, List.take_left' rfl] theorem lt_of_mem_innerEnds : ∀ (p : List (List Int)) (acc x : Nat), (∀ b ∈ p, b ≠ []) → x ∈ innerEnds acc p → acc < x := by intro p induction p with | nil => intro acc x _ hx; rw [innerEnds_nil] at hx; exact absurd hx List.not_mem_nil | cons a rest ih => intro acc x hne hx cases rest with | nil => rw [innerEnds_singleton] at hx; exact absurd hx List.not_mem_nil | cons b rest' => rw [innerEnds_cons_cons, List.mem_cons] at hx have hb : 1 ≤ a.length := one_le_length_of_ne_nil (hne a List.mem_cons_self) rcases hx with rfl | hx · omega · have := ih (acc + a.length) x (fun sub hsub => hne sub (List.mem_cons_of_mem _ hsub)) hx omega theorem mem_innerEnds_lt_total : ∀ (p : List (List Int)) (acc x : Nat), (∀ b ∈ p, b ≠ []) → x ∈ innerEnds acc p → x < acc + (p.map List.length).sum := by intro p induction p with | nil => intro acc x _ hx; rw [innerEnds_nil] at hx; exact absurd hx List.not_mem_nil | cons a rest ih => intro acc x hne hx cases rest with | nil => rw [innerEnds_singleton] at hx; exact absurd hx List.not_mem_nil | cons b rest' => rw [innerEnds_cons_cons, List.mem_cons] at hx have hb : 1 ≤ b.length := one_le_length_of_ne_nil (hne b (List.mem_cons_of_mem _ List.mem_cons_self)) have hsum : ((a :: b :: rest').map List.length).sum = a.length + ((b :: rest').map List.length).sum := by simp have hsum' : ((b :: rest').map List.length).sum = b.length + (rest'.map List.length).sum := by simp rcases hx with rfl | hx · omega · have := ih (acc + a.length) x (fun sub hsub => hne sub (List.mem_cons_of_mem _ hsub)) hx omega theorem innerEnds_pairwise_lt : ∀ (p : List (List Int)) (acc : Nat), (∀ b ∈ p, b ≠ []) → (innerEnds acc p).Pairwise (· < ·) := by intro p induction p with | nil => intro acc _; rw [innerEnds_nil]; exact List.Pairwise.nil | cons a rest ih => intro acc hne cases rest with | nil => rw [innerEnds_singleton]; exact List.Pairwise.nil | cons b rest' => have hne' : ∀ sub ∈ b :: rest', sub ≠ [] := fun sub hsub => hne sub (List.mem_cons_of_mem _ hsub) rw [innerEnds_cons_cons] exact List.Pairwise.cons (fun y hy => lt_of_mem_innerEnds (b :: rest') (acc + a.length) y hne' hy) (ih (acc + a.length) hne') theorem exists_code_of_split (nums : List Int) (blocks : List (List Int)) (hflat : blocks.flatten = nums) (hne : ∀ b ∈ blocks, b ≠ []) (hs : 0 < nums.length) : ∃ vec ∈ allBoolVecs (nums.length - 1), decodeSplit nums (fun i => vec.getD i.val false) = blocks := by have hsum : (blocks.map List.length).sum = nums.length := by rw [← List.length_flatten, hflat] have hp0 : blocks ≠ [] := by intro hpe rw [hpe] at hsum simp only [List.map_nil, List.sum_nil] at hsum omega have hb1 : ∀ x ∈ innerEnds 0 blocks, 1 ≤ x := by intro x hx have := lt_of_mem_innerEnds blocks 0 x hne hx omega have hb2 : ∀ x ∈ innerEnds 0 blocks, x < nums.length := by intro x hx have := mem_innerEnds_lt_total blocks 0 x hne hx omega refine ⟨(List.range (nums.length - 1)).map (fun j => decide (j + 1 ∈ innerEnds 0 blocks)), ?_, ?_⟩ · rw [mem_allBoolVecs_iff] simp · have hcuts : (fun i : Fin (nums.length - 1) => ((List.range (nums.length - 1)).map (fun j => decide (j + 1 ∈ innerEnds 0 blocks))).getD i.val false) = fun i : Fin (nums.length - 1) => decide (i.val + 1 ∈ innerEnds 0 blocks) := by funext i rw [List.getD_eq_getElem?_getD, List.getElem?_map, List.getElem?_range i.isLt] rfl have hnodup : ((List.range (nums.length - 1)).map (fun x => x + 1)).Nodup := List.Nodup.map (fun a b hab => by omega) List.nodup_range have hsub : (innerEnds 0 blocks).Sublist ((List.range (nums.length - 1)).map (fun x => x + 1)) := by have hT : ((innerEnds 0 blocks).map (fun x => x - 1)).Sublist (List.range (nums.length - 1)) := by refine sublist_range_of_pairwise_lt _ _ ?_ ?_ · rw [List.pairwise_map] refine (innerEnds_pairwise_lt blocks 0 hne).imp_of_mem ?_ intro u v hu _ huv have := hb1 u hu omega · intro y hy rw [List.mem_map] at hy obtain ⟨x, hx, rfl⟩ := hy have h1 := hb1 x hx have h2 := hb2 x hx omega have hmap : ((innerEnds 0 blocks).map (fun x => x - 1)).map (fun x => x + 1) = innerEnds 0 blocks := by rw [List.map_map] conv_rhs => rw [← List.map_id (innerEnds 0 blocks)] apply List.map_congr_left intro x hx have := hb1 x hx simp only [Function.comp_apply, id] omega have h3 := hT.map (fun x => x + 1) rw [hmap] at h3 exact h3 have hcp : cutPositions nums (fun i : Fin (nums.length - 1) => decide (i.val + 1 ∈ innerEnds 0 blocks)) = 0 :: (innerEnds 0 blocks ++ [nums.length]) := by unfold cutPositions rw [filterMap_finRange_boolMem (nums.length - 1) (innerEnds 0 blocks), filter_mem_eq_of_sublist hnodup hsub, List.cons_append] rw [hcuts] unfold decodeSplit rw [hcp] exact decodeAt_innerEnds nums blocks 0 hp0 (by simpa using hflat) /-! ### The checker's candidate list, named -/ /-- The enumerated candidate splits: the checker's `let valid`, named. -/ def validSplits (input : Input) : List (List (List Int)) := (allBoolVecs (input.1.length - 1)).filterMap (fun vec => if isValidSplitBool input.1 input.2 (decodeSplit input.1 (fun i => vec.getD i.val false)) then some (decodeSplit input.1 (fun i => vec.getD i.val false)) else none) theorem check_eq (input : Input) (result : Output) : splitArrayLargestSum_check input result = ((validSplits input).any (fun blocks => isGreatestSumBool blocks (result : Int)) && (validSplits input).all (fun blocks => (blockSums blocks).all (fun s => !((blockSums blocks).all (fun t => t ≤ s)) || ((result : Int) ≤ s)))) := rfl theorem mem_validSplits_iff (input : Input) (hlen : 0 < input.1.length) (blocks : List (List Int)) : blocks ∈ validSplits input ↔ IsValidSplit input.1 input.2 blocks := by rw [validSplits, List.mem_filterMap] constructor · rintro ⟨vec, _, heq⟩ by_cases hb : isValidSplitBool input.1 input.2 (decodeSplit input.1 (fun i => vec.getD i.val false)) = true · rw [if_pos hb] at heq have hbe : decodeSplit input.1 (fun i => vec.getD i.val false) = blocks := Option.some_inj.mp heq rw [← hbe] exact (isValidSplitBool_iff _ _ _).mp hb · rw [if_neg hb] at heq exact absurd heq (by simp) · intro hv obtain ⟨hflat, _, hne⟩ := hv obtain ⟨vec, hvec, heq⟩ := exists_code_of_split input.1 blocks hflat hne hlen refine ⟨vec, hvec, ?_⟩ rw [heq, if_pos ((isValidSplitBool_iff _ _ _).mpr ⟨hflat, ‹blocks.length = input.2›, hne⟩)] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem splitArrayLargestSum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : splitArrayLargestSum_check input result ↔ splitArrayLargestSum_spec input result := by have hlen : 0 < input.1.length := by simp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq] at h omega rw [check_eq] simp only [Bool.and_eq_true, List.any_eq_true, List.all_eq_true] constructor · rintro ⟨⟨blocks, hmem, hg⟩, hall⟩ refine ⟨⟨blocks, (mem_validSplits_iff input hlen blocks).mp hmem, (isGreatestSumBool_iff blocks _).mp hg⟩, ?_⟩ rintro m ⟨blocks', hv', hg'⟩ exact (all_max_iff blocks' _).mp (hall blocks' ((mem_validSplits_iff input hlen blocks').mpr hv')) m hg' · rintro ⟨⟨blocks, hv, hg⟩, hlb⟩ refine ⟨⟨blocks, (mem_validSplits_iff input hlen blocks).mpr hv, (isGreatestSumBool_iff blocks _).mpr hg⟩, ?_⟩ intro blocks' hmem' refine (all_max_iff blocks' _).mpr ?_ intro m hgm exact hlb ⟨blocks', (mem_validSplits_iff input hlen blocks').mp hmem', hgm⟩ /-! ### Implementation helpers -/ /-- Greedy count of contiguous blocks with sums at most `limit`, starting a new block exactly when the running sum plus the next element would exceed `limit`. -/ def greedyBlockCount (limit : Int) (cur : Int) (count : Nat) : List Int → Nat | [] => count | x :: xs => if cur + x ≤ limit then greedyBlockCount limit (cur + x) count xs else greedyBlockCount limit x (count + 1) xs /-- Feasibility test: every element fits under `limit` and the greedy scan uses at most `k` non-empty blocks. -/ def canSplitWithin (limit : Nat) (k : Nat) (nums : List Int) : Bool := nums.all (fun x => x ≤ (limit : Int)) && greedyBlockCount (limit : Int) 0 1 nums ≤ k /-- Binary search on `[lo, hi]` for the least limit at which `nums` splits into at most `k` blocks; each round replaces `hi` by `mid` or `lo` by `mid + 1`. -/ def binSearch (k : Nat) (nums : List Int) (lo hi : Nat) : Nat := if h : lo < hi then if canSplitWithin ((lo + hi) / 2) k nums then binSearch k nums lo ((lo + hi) / 2) else binSearch k nums ((lo + hi) / 2 + 1) hi else lo termination_by hi - lo decreasing_by · omega · omega /-! ### Main algorithm (impl) -/ /-- Binary search over `[max element, total sum]` for the least feasible largest block sum, using the greedy block count as the feasibility oracle. -/ def minLargestSum (input : Input) : Output := let nums := input.1 let lo := (nums.foldl (fun m x => max m x) (0 : Int)).toNat let hi := nums.sum.toNat binSearch input.2 nums lo hi /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem minLargestSum_correct (input : Input) (h : isValidInput input) : splitArrayLargestSum_spec input (minLargestSum input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([7, 2, 5, 10, 8], 2) #guard isValidInput ([1, 2, 3, 4, 5], 2) #guard isValidInput ([1, 4, 4], 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([(-1)], 1)) #guard !(isValidInput ([1000001], 1)) #guard !(isValidInput ([1, 2, 3], 4)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard splitArrayLargestSum_check ([7, 2, 5, 10, 8], 2) 18 #guard splitArrayLargestSum_check ([1, 2, 3, 4, 5], 2) 9 #guard splitArrayLargestSum_check ([1, 4, 4], 3) 4 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(splitArrayLargestSum_check ([7, 2, 5, 10, 8], 2) 23) #guard !(splitArrayLargestSum_check ([1, 2, 3, 4, 5], 2) 12) #guard !(splitArrayLargestSum_check ([1, 4, 4], 3) 9) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard minLargestSum ([7, 2, 5, 10, 8], 2) == 18 #guard minLargestSum ([1, 2, 3, 4, 5], 2) == 9 #guard minLargestSum ([1, 4, 4], 3) == 4 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard splitArrayLargestSum_check ([7, 2, 5, 10, 8], 2) (minLargestSum ([7, 2, 5, 10, 8], 2)) #guard splitArrayLargestSum_check ([1, 2, 3, 4, 5], 2) (minLargestSum ([1, 2, 3, 4, 5], 2)) #guard splitArrayLargestSum_check ([1, 4, 4], 3) (minLargestSum ([1, 4, 4], 3)) end PSplitArrayLargestSum