import Mathlib /-! # Maximum Subarray Given an integer array nums, find the subarray with the largest sum, and return its sum. ## Constraints - 1 <= nums.length <= 10^5 - -10^4 <= nums[i] <= 10^4 ## Provided examples - `nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]` → `6` - `nums = [1]` → `1` - `nums = [5, 4, -1, 7, 8]` → `23` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 10^5. empty where at least one element is required) - invalid input: `nums = [10001]` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one past the stated maximum) - invalid input: `nums = [-10001]` ([structural] a predicate that admits -10^4 <= nums[i] <= 10^4. one below the stated minimum) - `nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]` → `7` is wrong ([structural] no subarray is required to attain the returned sum. no contiguous subarray sums to 7) - `nums = [1]` → `2` is wrong ([structural] maximum stated as a bound; no subarray is required to attain it. 2 exceeds every subarray sum but no subarray sums to 2) - `nums = [5, 4, -1, 7, 8]` → `18` is wrong ([structural] maximality stated as achievability alone. 18 is a subarray sum but not the largest) -/ namespace PMaximumSubarray abbrev Input := List Int abbrev Output := Int /-! ### Specification helpers -/ /-- `sub` is a contiguous, non-empty segment of `nums`. -/ def IsSubarray (nums sub : List Int) : Prop := sub <:+: nums ∧ sub ≠ [] /-! ### Validity predicate (V) -/ /-- Valid input: 1 ≤ length ≤ 10^5 and every element between -10^4 and 10^4. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10^5 && input.all (fun x => -10^4 ≤ x && x ≤ 10^4) /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest sum attained by any contiguous non-empty subarray of `input`: some subarray sums to it, and none sums higher. -/ def maxSubarraySum_spec (input : Input) (result : Output) : Prop := IsGreatest {s | ∃ sub : List Int, IsSubarray input sub ∧ sub.sum = s} result /-! ### Decidable specification (P_check) -/ /-- The sum of the contiguous block of `input` from index `i` to index `j` inclusive. -/ def windowSum (input : Input) (i j : Nat) : Int := ((input.drop i).take (j - i + 1)).sum /-- Executable checker for `maxSubarraySum_spec` over endpoint-pair codes. -/ def maxSubarraySum_check (input : Input) (result : Output) : Bool := decide ((∃ p : Fin input.length × Fin input.length, p.1.val ≤ p.2.val ∧ windowSum input p.1.val p.2.val = result) ∧ (∀ p : Fin input.length × Fin input.length, p.1.val ≤ p.2.val → windowSum input p.1.val p.2.val ≤ result)) theorem window_isSubarray (input : List Int) (i j : Nat) (hij : i ≤ j) (hj : j < input.length) : IsSubarray input ((input.drop i).take (j - i + 1)) := by unfold IsSubarray refine ⟨(List.take_prefix _ _).isInfix.trans (List.drop_suffix i input).isInfix, ?_⟩ apply List.ne_nil_of_length_pos simp only [List.length_take, List.length_drop] omega theorem exists_window_of_isSubarray (input sub : List Int) (hsub : IsSubarray input sub) : ∃ i j : Nat, i ≤ j ∧ j < input.length ∧ windowSum input i j = sub.sum := by obtain ⟨⟨s, t, hst⟩, hne⟩ := hsub subst hst have hlen : 0 < sub.length := List.length_pos_iff.mpr hne refine ⟨s.length, s.length + sub.length - 1, by omega, ?_, ?_⟩ · simp only [List.length_append] omega · unfold windowSum have hdrop : (s ++ sub ++ t).drop s.length = sub ++ t := by rw [List.append_assoc, List.drop_left] rw [hdrop] have hk : s.length + sub.length - 1 - s.length + 1 = sub.length := by omega rw [hk, List.take_left] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxSubarraySum_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxSubarraySum_check input result ↔ maxSubarraySum_spec input result := by simp only [maxSubarraySum_check, maxSubarraySum_spec, decide_eq_true_eq] constructor · rintro ⟨⟨p, hple, hpsum⟩, hub⟩ refine ⟨⟨_, window_isSubarray input p.1.val p.2.val hple p.2.isLt, hpsum⟩, ?_⟩ rintro s ⟨sub, hsub, rfl⟩ obtain ⟨i, j, hij, hj, hw⟩ := exists_window_of_isSubarray input sub hsub have hle := hub (⟨i, by omega⟩, ⟨j, hj⟩) hij rw [hw] at hle exact hle · rintro ⟨⟨sub, hsub, hsum⟩, hub⟩ refine ⟨?_, ?_⟩ · obtain ⟨i, j, hij, hj, hw⟩ := exists_window_of_isSubarray input sub hsub exact ⟨(⟨i, by omega⟩, ⟨j, hj⟩), hij, by rw [hw, hsum]⟩ · intro p hple exact hub ⟨_, window_isSubarray input p.1.val p.2.val hple p.2.isLt, rfl⟩ /-! ### Implementation helpers -/ /-- Kadane's loop over `xs`: `cur` is the maximum sum of a subarray ending at the previous element, `best` the maximum seen so far. -/ def maxSubarrayHelper (cur best : Int) (xs : List Int) : Int := match xs with | [] => best | x :: xs => let cur' := max x (cur + x) let best' := max best cur' maxSubarrayHelper cur' best' xs /-! ### Main algorithm (impl) -/ /-- Maximum subarray sum by Kadane's algorithm: one pass keeping the best sum ending here and the best overall. -/ def findMaxSubarray (nums : List Int) : Int := match nums with | [] => 0 | x :: xs => maxSubarrayHelper x x xs /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findMaxSubarray_correct (input : Input) (h : isValidInput input) : maxSubarraySum_spec input (findMaxSubarray input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [-2, 1, -3, 4, -1, 2, 1, -5, 4] #guard isValidInput [1] #guard isValidInput [5, 4, -1, 7, 8] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [10001]) #guard !(isValidInput [-10001]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxSubarraySum_check [(-2), 1, (-3), 4, (-1), 2, 1, (-5), 4] 6 #guard maxSubarraySum_check [1] 1 #guard maxSubarraySum_check [5, 4, (-1), 7, 8] 23 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxSubarraySum_check [(-2), 1, (-3), 4, (-1), 2, 1, (-5), 4] 7) #guard !(maxSubarraySum_check [1] 2) #guard !(maxSubarraySum_check [5, 4, (-1), 7, 8] 18) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findMaxSubarray [(-2), 1, (-3), 4, (-1), 2, 1, (-5), 4] == 6 #guard findMaxSubarray [1] == 1 #guard findMaxSubarray [5, 4, (-1), 7, 8] == 23 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxSubarraySum_check [(-2), 1, (-3), 4, (-1), 2, 1, (-5), 4] (findMaxSubarray [(-2), 1, (-3), 4, (-1), 2, 1, (-5), 4]) #guard maxSubarraySum_check [1] (findMaxSubarray [1]) #guard maxSubarraySum_check [5, 4, (-1), 7, 8] (findMaxSubarray [5, 4, (-1), 7, 8]) end PMaximumSubarray