import Mathlib /-! # Number Of Longest Increasing Subsequence Given an integer array nums, return the number of longest increasing subsequences. Notice that the sequence has to be strictly increasing. ## Constraints - 1 <= nums.length <= 2000 - -10^6 <= nums[i] <= 10^6 - The answer is guaranteed to fit inside a 32-bit integer. ## Provided examples - `nums = [1, 3, 5, 4, 7]` → `2` - `nums = [2, 2, 2, 2, 2]` → `5` - `nums = [1]` → `1` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 2000. empty array breaks the length floor) - invalid input: `nums = [-1000001]` ([structural] a predicate that admits -10^6 <= nums[i] <= 10^6. one below the minimum value) - invalid input: `nums = [2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, 18, 17, 20, 19, 22, 21, 24, 23, 26, 25, 28, 27, 30, 29, 32, 31, 34, 33, 36, 35, 38, 37, 40, 39, 42, 41, 44, 43, 46, 45, 48, 47, 50, 49, 52, 51, 54, 53, 56, 55, 58, 57, 60, 59, 62, 61]` ([structural] a predicate that admits The answer is guaranteed to fit inside a 32-bit integer.. 2^31 LIS, one past signed 32-bit max; size/value predicates accept it) - `nums = [1, 3, 5, 4, 7]` → `3` is wrong ([structural] malformed_shape not applicable to int; off-by-one counts an extra LIS. Overcounts the two true LIS by one) - `nums = [2, 2, 2, 2, 2]` → `4` is wrong ([structural] loop bound is off by one and never processes the last index. counts only the first four single-element longest subsequences) - `nums = [1]` → `0` is wrong ([structural] does not require at least one LIS to be counted on a nonempty array. zero passes when no completeness floor is stated) -/ namespace PNumberOfLongestIncreasingSubsequence abbrev Input := List Int abbrev Output := Nat /-! ### Specification helpers -/ /-- Pairs each element of `nums` with the length of a longest strictly increasing subsequence ending there and the number of such subsequences ending there. -/ def lisEndCounts (nums : List Int) : List (Nat × Nat) := let step (acc : List (Int × Nat × Nat)) (x : Int) : List (Int × Nat × Nat) := let smaller := acc.filter (fun p => p.1 < x) let best := smaller.foldl (fun m p => max m p.2.1) 0 let cnt := (smaller.filter (fun p => p.2.1 == best)).foldl (fun s p => s + p.2.2) 0 acc ++ [(x, best + 1, max cnt 1)] (nums.foldl step []).map Prod.snd /-- The number of longest strictly increasing subsequences of `nums`, with equal values at different positions counted as distinct. -/ def countLIS (nums : List Int) : Nat := let pairs := lisEndCounts nums let maxLen := pairs.foldl (fun m p => max m p.1) 0 (pairs.filter (fun p => p.1 == maxLen)).foldl (fun s p => s + p.2) 0 /-- `idx` lists in-bounds positions of `nums` in strictly increasing order whose selected values are strictly increasing. -/ def isIncreasingSubseqIndices (nums : List Int) (idx : List Nat) : Prop := (∀ i ∈ idx, i < nums.length) ∧ idx.SortedLT ∧ (idx.map (fun i => (nums[i]?).getD 0)).SortedLT /-- `idx` selects a longest strictly increasing subsequence of `nums` by position: it selects one and its length is greatest among all selectable lengths. -/ def IsLIS (nums : List Int) (idx : List Nat) : Prop := isIncreasingSubseqIndices nums idx ∧ IsGreatest {n : Nat | ∃ jdx : List Nat, isIncreasingSubseqIndices nums jdx ∧ jdx.length = n} idx.length /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 2000 elements, each between -10^6 and 10^6, with at most 2147483647 longest increasing subsequences. -/ def isValidInput (nums : Input) : Bool := 1 ≤ nums.length && nums.length ≤ 2000 && nums.all (fun x => -1000000 ≤ x && x ≤ 1000000) && countLIS nums ≤ 2147483647 /-! ### Ideal specification (P_spec) -/ /-- `result` is the number of longest increasing subsequences of `input`: some finite collection of index sequences has cardinality `result` and contains an index sequence exactly when it satisfies `IsLIS`. -/ def numberOfLongestIncreasingSubsequences_spec (input : Input) (result : Output) : Prop := ∃ s : Finset (List Nat), s.card = result ∧ ∀ idx : List Nat, idx ∈ s ↔ IsLIS input idx /-! ### Decidable specification (P_check) -/ /-- The index lists that select positions of `input`: the sublists of `List.range input.length`. -/ def indexSelections (input : Input) : List (List Nat) := (List.range input.length).sublists /-- `idx` selects a strictly increasing subsequence of `input` whose length bounds the length of every increasing subsequence selected by an index list in `indexSelections input`. -/ def isLISAmongSelections (input : Input) (idx : List Nat) : Prop := isIncreasingSubseqIndices input idx ∧ ∀ jdx ∈ indexSelections input, isIncreasingSubseqIndices input jdx → jdx.length ≤ idx.length /-- Boolean test for `isIncreasingSubseqIndices`: in-bounds positions, strictly increasing indices, strictly increasing selected values. -/ def isIncreasingSubseqIndicesBool (input : Input) (idx : List Nat) : Bool := let vals := idx.map fun i => (input[i]?).getD 0 idx.all (fun i => i < input.length) && (idx.zip idx.tail).all (fun p => p.1 < p.2) && (vals.zip vals.tail).all (fun p => p.1 < p.2) /-- Boolean test for `isLISAmongSelections`: `idx` selects an increasing subsequence and no index list in `indexSelections input` selects a longer one. -/ def isLISAmongSelectionsBool (input : Input) (idx : List Nat) : Bool := isIncreasingSubseqIndicesBool input idx && (indexSelections input).all (fun jdx => !isIncreasingSubseqIndicesBool input jdx || jdx.length ≤ idx.length) /-- The finite collection of index lists selecting a longest strictly increasing subsequence of `input`. -/ def lisIndexCollection (input : Input) : Finset (List Nat) := ((indexSelections input).filter fun idx => isLISAmongSelectionsBool input idx).toFinset /-- Executable checker for `numberOfLongestIncreasingSubsequences_spec` over the index lists in `indexSelections input`. -/ def numberOfLongestIncreasingSubsequences_check (input : Input) (result : Output) : Bool := let s := lisIndexCollection input s.card == result && (indexSelections input).all (fun idx => decide (idx ∈ s) == isLISAmongSelectionsBool input idx) theorem root_of_bridges (input : Input) (result : Output) (bridge : ∀ idx, idx ∈ lisIndexCollection input ↔ IsLIS input idx) : numberOfLongestIncreasingSubsequences_check input result ↔ numberOfLongestIncreasingSubsequences_spec input result := by have hc : numberOfLongestIncreasingSubsequences_check input result ↔ (lisIndexCollection input).card = result := by simp [numberOfLongestIncreasingSubsequences_check, lisIndexCollection] grind only [] rw [hc] constructor · intro h exact ⟨lisIndexCollection input, h, bridge⟩ · rintro ⟨s, hs, hm⟩ have he : s = lisIndexCollection input := by ext idx exact (hm idx).trans (bridge idx).symm simpa [he] using hs theorem adjacent_sorted {α : Type*} [LinearOrder α] (l : List α) : (l.zip l.tail).all (fun p => decide (p.1 < p.2)) = true ↔ l.SortedLT := by rw [List.sortedLT_iff_isChain] induction l with | nil => simp | cons a l ih => cases l with | nil => simp | cons b l => simpa only [List.tail_cons, List.zip_cons_cons, List.all_cons, Bool.and_eq_true, decide_eq_true_eq, List.isChain_cons_cons] using (and_congr (Iff.rfl : a < b ↔ a < b) ih) theorem increasing_bool (input : Input) (idx : List Nat) : isIncreasingSubseqIndicesBool input idx = true ↔ isIncreasingSubseqIndices input idx := by simp only [isIncreasingSubseqIndicesBool, isIncreasingSubseqIndices, Bool.and_eq_true, adjacent_sorted] simp only [List.all_eq_true, decide_eq_true_eq, and_assoc] theorem selection_complete (input : Input) (idx : List Nat) (hi : isIncreasingSubseqIndices input idx) : idx ∈ indexSelections input := by apply List.mem_sublists.mpr apply List.sublist_of_subperm_of_sortedLE · apply List.subperm_of_subset hi.2.1.nodup intro i hm exact List.mem_range.mpr (hi.1 i hm) · exact hi.2.1.sortedLE · exact (List.sortedLT_range input.length).sortedLE theorem lis_bool (input : Input) (idx : List Nat) : isLISAmongSelectionsBool input idx = true ↔ IsLIS input idx := by simp only [isLISAmongSelectionsBool, Bool.and_eq_true, List.all_eq_true, Bool.or_eq_true, Bool.not_eq_true', increasing_bool, decide_eq_true_eq] constructor · rintro ⟨hi, hm⟩ refine ⟨hi, ⟨idx, hi, rfl⟩, ?_⟩ rintro n ⟨jdx, hj, rfl⟩ have ht := hm jdx (selection_complete input jdx hj) have hb := (increasing_bool input jdx).mpr hj simp [hb] at ht exact ht · rintro ⟨hi, hmax⟩ refine ⟨hi, ?_⟩ intro jdx hj by_cases hb : isIncreasingSubseqIndicesBool input jdx = true · exact Or.inr (hmax.2 ⟨jdx, (increasing_bool input jdx).mp hb, rfl⟩) · exact Or.inl (by cases he : isIncreasingSubseqIndicesBool input jdx <;> simp_all) theorem membership_bridge (input : Input) (idx : List Nat) : idx ∈ lisIndexCollection input ↔ IsLIS input idx := by simp only [lisIndexCollection, List.mem_toFinset, List.mem_filter, lis_bool] exact ⟨fun h => h.2, fun h => ⟨selection_complete input idx h.1, h⟩⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numberOfLongestIncreasingSubsequences_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numberOfLongestIncreasingSubsequences_check input result ↔ numberOfLongestIncreasingSubsequences_spec input result := by exact root_of_bridges input result (membership_bridge input) /-! ### Main algorithm (impl) -/ /-- Count of longest strictly increasing subsequences by the quadratic dynamic program in `countLIS`. -/ def countLongestIncreasingSubsequences (nums : Input) : Output := countLIS nums /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countLongestIncreasingSubsequences_correct (input : Input) (h : isValidInput input) : numberOfLongestIncreasingSubsequences_spec input (countLongestIncreasingSubsequences input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [1, 3, 5, 4, 7] #guard isValidInput [2, 2, 2, 2, 2] #guard isValidInput [1] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [(-1000001)]) #guard !(isValidInput [2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13, 16, 15, 18, 17, 20, 19, 22, 21, 24, 23, 26, 25, 28, 27, 30, 29, 32, 31, 34, 33, 36, 35, 38, 37, 40, 39, 42, 41, 44, 43, 46, 45, 48, 47, 50, 49, 52, 51, 54, 53, 56, 55, 58, 57, 60, 59, 62, 61]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numberOfLongestIncreasingSubsequences_check [1, 3, 5, 4, 7] 2 #guard numberOfLongestIncreasingSubsequences_check [2, 2, 2, 2, 2] 5 #guard numberOfLongestIncreasingSubsequences_check [1] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numberOfLongestIncreasingSubsequences_check [1, 3, 5, 4, 7] 3) #guard !(numberOfLongestIncreasingSubsequences_check [2, 2, 2, 2, 2] 4) #guard !(numberOfLongestIncreasingSubsequences_check [1] 0) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countLongestIncreasingSubsequences [1, 3, 5, 4, 7] == 2 #guard countLongestIncreasingSubsequences [2, 2, 2, 2, 2] == 5 #guard countLongestIncreasingSubsequences [1] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numberOfLongestIncreasingSubsequences_check [1, 3, 5, 4, 7] (countLongestIncreasingSubsequences [1, 3, 5, 4, 7]) #guard numberOfLongestIncreasingSubsequences_check [2, 2, 2, 2, 2] (countLongestIncreasingSubsequences [2, 2, 2, 2, 2]) #guard numberOfLongestIncreasingSubsequences_check [1] (countLongestIncreasingSubsequences [1]) end PNumberOfLongestIncreasingSubsequence