import Mathlib /-! # Maximum Sum Of Two Non Overlapping Subarrays Given an integer array nums and two integers firstLen and secondLen, return the maximum sum of elements in two non-overlapping subarrays with lengths firstLen and secondLen. The array with length firstLen could occur before or after the array with length secondLen, but they have to be non-overlapping. A subarray is a contiguous part of an array. ## Constraints - 1 <= firstLen, secondLen <= 1000 - 2 <= firstLen + secondLen <= 1000 - firstLen + secondLen <= nums.length <= 1000 - 0 <= nums[i] <= 1000 ## Provided examples - `nums = [0, 6, 5, 2, 2, 5, 1, 9, 4], firstLen = 1, secondLen = 2` → `20` - `nums = [3, 8, 1, 3, 2, 1, 8, 9, 0], firstLen = 3, secondLen = 2` → `29` - `nums = [2, 1, 5, 6, 0, 9, 5, 0, 3, 8], firstLen = 4, secondLen = 3` → `31` ## Synthesized negative examples - invalid input: `nums = [1, 2], firstLen = 0, secondLen = 2` ([structural] a predicate that admits 1 <= firstLen, secondLen <= 1000. firstLen one below minimum; predicate forgetting lower bound accepts it) - invalid input: `nums = [1], firstLen = 1, secondLen = 2` ([structural] a predicate that admits firstLen + secondLen <= nums.length <= 1000. sum exceeds nums.length; predicate checking lengths alone accepts it) - invalid input: `nums = [-1, 0], firstLen = 1, secondLen = 1` ([structural] a predicate that admits 0 <= nums[i] <= 1000. negative element; predicate checking only upper bound accepts it) - `nums = [0, 6, 5, 2, 2, 5, 1, 9, 4], firstLen = 1, secondLen = 2` → `21` is wrong ([structural] maximum is stated as an upper bound without requiring it to be attained. no non-overlapping pair sums to 21) - `nums = [3, 8, 1, 3, 2, 1, 8, 9, 0], firstLen = 3, secondLen = 2` → `28` is wrong ([structural] maximality stated as achievability alone. 28 is achievable by valid non-overlapping subarrays but 29 is better) - `nums = [2, 1, 5, 6, 0, 9, 5, 0, 3, 8], firstLen = 4, secondLen = 3` → `30` is wrong ([structural] answer is one less than the true maximum. 30 is the true max minus one) -/ namespace PMaximumSumOfTwoNonOverlappingSubarrays abbrev Input := (List Int) × (Nat) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- Starting positions `i` and `j` describe two in-bounds, non-overlapping contiguous subarrays of `nums` with lengths `firstLen` and `secondLen`. -/ def IsNonOverlappingSubarrayPair (nums : List Int) (firstLen secondLen i j : Nat) : Prop := i + firstLen ≤ nums.length ∧ j + secondLen ≤ nums.length ∧ (i + firstLen ≤ j ∨ j + secondLen ≤ i) /-- The combined sum of the subarray of length `firstLen` starting at `i` and the subarray of length `secondLen` starting at `j`. -/ def pairSum (nums : List Int) (firstLen secondLen i j : Nat) : Int := ((nums.drop i).take firstLen).sum + ((nums.drop j).take secondLen).sum /-! ### Validity predicate (V) -/ /-- Valid input: both lengths in `[1, 1000]` with sum in `[2, 1000]` and at most `nums.length`, `nums` of length at most 1000, and every element in `[0, 1000]`. -/ def isValidInput (input : Input) : Bool := let nums := input.1 let firstLen := input.2.1 let secondLen := input.2.2 1 ≤ firstLen && firstLen ≤ 1000 && 1 ≤ secondLen && secondLen ≤ 1000 && 2 ≤ firstLen + secondLen && firstLen + secondLen ≤ 1000 && firstLen + secondLen ≤ nums.length && nums.length ≤ 1000 && nums.all fun x => 0 ≤ x && x ≤ 1000 /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest combined sum attained by any pair of non-overlapping contiguous subarrays of lengths `firstLen` and `secondLen`. -/ def maxSumTwoNoOverlap_spec (input : Input) (result : Output) : Prop := IsGreatest {s : Nat | ∃ i j : Nat, IsNonOverlappingSubarrayPair input.1 input.2.1 input.2.2 i j ∧ pairSum input.1 input.2.1 input.2.2 i j = s} result /-! ### Decidable specification (P_check) -/ /-- Decides `IsNonOverlappingSubarrayPair`: it unfolds to a conjunction of `Nat` inequalities and a disjunction of `Nat` inequalities, all of which Lean decides directly. Needed because instance resolution does not unfold the `def` on its own. -/ instance instDecidableIsNonOverlappingSubarrayPair (nums : List Int) (firstLen secondLen i j : Nat) : Decidable (IsNonOverlappingSubarrayPair nums firstLen secondLen i j) := inferInstanceAs (Decidable (i + firstLen ≤ nums.length ∧ j + secondLen ≤ nums.length ∧ (i + firstLen ≤ j ∨ j + secondLen ≤ i))) /-- Decides `maxSumTwoNoOverlap_spec`: membership of `result` in the set of attainable pair sums becomes a bounded search over start positions `i, j < nums.length + 1` (the `IsNonOverlappingSubarrayPair` in-bounds conditions force this bound), and the `upperBounds` half becomes the same bounded check that every attainable pair sum is at most `result`. -/ instance instDecidableMaxSumTwoNoOverlap_spec (input : Input) (result : Output) : Decidable (IsGreatest {s : Nat | ∃ i j : Nat, IsNonOverlappingSubarrayPair input.1 input.2.1 input.2.2 i j ∧ pairSum input.1 input.2.1 input.2.2 i j = (s : Int)} result) := decidable_of_iff ((∃ i < input.1.length + 1, ∃ j < input.1.length + 1, (IsNonOverlappingSubarrayPair input.1 input.2.1 input.2.2 i j ∧ pairSum input.1 input.2.1 input.2.2 i j = (result : Int))) ∧ (∀ i < input.1.length + 1, ∀ j < input.1.length + 1, IsNonOverlappingSubarrayPair input.1 input.2.1 input.2.2 i j → pairSum input.1 input.2.1 input.2.2 i j ≤ (result : Int))) (by constructor · rintro ⟨⟨i, hi, j, hj, hnop, heq⟩, hub⟩ refine ⟨⟨i, j, hnop, heq⟩, fun {y} hy => ?_⟩ obtain ⟨i', j', hnop', heq'⟩ := hy have hi' : i' < input.1.length + 1 := Nat.lt_succ_of_le ((Nat.le_add_right i' input.2.1).trans hnop'.1) have hj' : j' < input.1.length + 1 := Nat.lt_succ_of_le ((Nat.le_add_right j' input.2.2).trans hnop'.2.1) have h := hub i' hi' j' hj' hnop' rw [heq'] at h omega · intro h obtain ⟨i, j, hnop, heq⟩ := h.1 have hi : i < input.1.length + 1 := Nat.lt_succ_of_le ((Nat.le_add_right i input.2.1).trans hnop.1) have hj : j < input.1.length + 1 := Nat.lt_succ_of_le ((Nat.le_add_right j input.2.2).trans hnop.2.1) refine ⟨⟨i, hi, j, hj, hnop, heq⟩, ?_⟩ intro i' _ j' _ hnop' by_cases h0 : 0 ≤ pairSum input.1 input.2.1 input.2.2 i' j' · have hmem' : (pairSum input.1 input.2.1 input.2.2 i' j').toNat ∈ {s : Nat | ∃ i j : Nat, IsNonOverlappingSubarrayPair input.1 input.2.1 input.2.2 i j ∧ pairSum input.1 input.2.1 input.2.2 i j = (s : Int)} := ⟨i', j', hnop', by rw [Int.toNat_of_nonneg h0]⟩ have hle := h.2 hmem' rw [← Int.toNat_of_nonneg h0] exact Int.ofNat_le.mpr hle · omega) /-- Executable checker obtained mechanically from the specification. -/ def maxSumTwoNoOverlap_check (input : Input) (result : Output) : Bool := @decide (maxSumTwoNoOverlap_spec input result) (by unfold maxSumTwoNoOverlap_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxSumTwoNoOverlap_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxSumTwoNoOverlap_check input result ↔ maxSumTwoNoOverlap_spec input result := by simp [maxSumTwoNoOverlap_check] /-! ### Implementation helpers -/ /-- Cumulative sums of `nums` with a leading zero, so entry `i` is the sum of the first `i` elements. -/ def prefixSums (nums : List Int) : List Int := nums.scanl (fun a b : Int => a + b) 0 /-- Start index paired with the element sum of every contiguous length-`k` subarray of `nums`. -/ def windowSums (nums : List Int) (k : Nat) : List (Nat × Int) := let ps := prefixSums nums (ps.zip (ps.drop k)).zipIdx.map fun ((lo, hi), i) => (i, hi - lo) /-- Greatest combined sum over all pairs of window entries whose starts satisfy the non-overlap predicate. -/ def bestPairSum (nums : List Int) (firstLen secondLen : Nat) (firstSums secondSums : List (Nat × Int)) : Int := firstSums.foldl (fun best (i, si) => secondSums.foldl (fun b (j, sj) => if IsNonOverlappingSubarrayPair nums firstLen secondLen i j then max b (si + sj) else b) best) 0 /-! ### Main algorithm (impl) -/ /-- Maximum combined sum by enumerating precomputed window-sum pairs and filtering on the spec's non-overlap predicate. -/ def maxSumTwoNoOverlapImpl (input : Input) : Output := let nums := input.1 let firstLen := input.2.1 let secondLen := input.2.2 (bestPairSum nums firstLen secondLen (windowSums nums firstLen) (windowSums nums secondLen)).toNat /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem maxSumTwoNoOverlapImpl_correct (input : Input) (h : isValidInput input) : maxSumTwoNoOverlap_spec input (maxSumTwoNoOverlapImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2) #guard isValidInput ([3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2) #guard isValidInput ([2, 1, 5, 6, 0, 9, 5, 0, 3, 8], 4, 3) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([1, 2], 0, 2)) #guard !(isValidInput ([1], 1, 2)) #guard !(isValidInput ([(-1), 0], 1, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxSumTwoNoOverlap_check ([0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2) 20 #guard maxSumTwoNoOverlap_check ([3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2) 29 #guard maxSumTwoNoOverlap_check ([2, 1, 5, 6, 0, 9, 5, 0, 3, 8], 4, 3) 31 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxSumTwoNoOverlap_check ([0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2) 21) #guard !(maxSumTwoNoOverlap_check ([3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2) 28) #guard !(maxSumTwoNoOverlap_check ([2, 1, 5, 6, 0, 9, 5, 0, 3, 8], 4, 3) 30) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard maxSumTwoNoOverlapImpl ([0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2) == 20 #guard maxSumTwoNoOverlapImpl ([3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2) == 29 #guard maxSumTwoNoOverlapImpl ([2, 1, 5, 6, 0, 9, 5, 0, 3, 8], 4, 3) == 31 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxSumTwoNoOverlap_check ([0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2) (maxSumTwoNoOverlapImpl ([0, 6, 5, 2, 2, 5, 1, 9, 4], 1, 2)) #guard maxSumTwoNoOverlap_check ([3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2) (maxSumTwoNoOverlapImpl ([3, 8, 1, 3, 2, 1, 8, 9, 0], 3, 2)) #guard maxSumTwoNoOverlap_check ([2, 1, 5, 6, 0, 9, 5, 0, 3, 8], 4, 3) (maxSumTwoNoOverlapImpl ([2, 1, 5, 6, 0, 9, 5, 0, 3, 8], 4, 3)) end PMaximumSumOfTwoNonOverlappingSubarrays