import Mathlib /-! # Best Time To Buy And Sell Stock With Transaction Fee You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). The transaction fee is only charged once for each stock purchase and sale. ## Constraints - 1 <= prices.length <= 5 * 10^4 - 1 <= prices[i] < 5 * 10^4 - 0 <= fee < 5 * 10^4 ## Provided examples - `prices = [1, 3, 2, 8, 4, 9], fee = 2` → `8` - `prices = [1, 3, 7, 5, 10, 3], fee = 3` → `6` - `prices = [1, 2, 3, 4, 5], fee = 1` → `3` ## Synthesized negative examples - invalid input: `prices = [], fee = 0` ([structural] a predicate that admits 1 <= prices.length <= 5 * 10^4. empty where at least one element is required) - invalid input: `prices = [0], fee = 0` ([structural] a predicate that admits 1 <= prices[i] < 5 * 10^4. one below the minimum price) - invalid input: `prices = [50000], fee = 0` ([structural] a predicate that admits 1 <= prices[i] < 5 * 10^4. equal to the stated maximum price) - `prices = [1, 3, 2, 8, 4, 9], fee = 2` → `7` is wrong ([structural] maximality stated as achievability alone. 7 is attainable by two transactions but is not the maximum) - `prices = [1, 3, 7, 5, 10, 3], fee = 3` → `7` is wrong ([structural] profit target one step above the true maximum. no fee-3 schedule reaches 7) - `prices = [1, 2, 3, 4, 5], fee = 1` → `2` is wrong ([structural] maximality stated as achievability alone. 2 is attainable but not the maximum) -/ namespace PBestTimeToBuyAndSellStockWithTransactionFee abbrev Input := (List Int) × (Int) abbrev Output := Int /-! ### Specification helpers -/ /-- A valid plan: each pair buys strictly before it sells with the sell day in bounds, and each sell precedes the next buy. -/ def IsValidTransactionPlan (prices : List Int) (plan : List (Nat × Nat)) : Prop := (∀ p ∈ plan, p.1 < p.2 ∧ p.2 < prices.length) ∧ plan.Chain' (fun a b => a.2 < b.1) /-- Total profit of a plan: over each pair, the sell price minus the buy price minus the fee. -/ def planProfit (prices : List Int) (fee : Int) (plan : List (Nat × Nat)) : Int := (plan.map fun p => (prices[p.2]?.getD 0) - (prices[p.1]?.getD 0) - fee).sum /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty price list of length at most 5·10⁴, prices in [1, 5·10⁴), fee in [0, 5·10⁴). -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 5 * 10 ^ 4 && input.1.all (fun p => 1 ≤ p && p < 5 * 10 ^ 4) && 0 ≤ input.2 && input.2 < 5 * 10 ^ 4 /-! ### Ideal specification (P_spec) -/ /-- `result` is the greatest profit attained by any valid transaction plan on `input`. -/ def maxProfit_spec (input : Input) (result : Output) : Prop := IsGreatest {k | ∃ plan : List (Nat × Nat), IsValidTransactionPlan input.1 plan ∧ planProfit input.1 input.2 plan = k} result /-! ### Decidable specification (P_check) -/ /-- One action per day: 0 for nothing, 1 for buy, 2 for sell; alternating codes biject with valid plans. -/ abbrev ActionCode (n : Nat) : Type := Fin n → Fin 3 /-- The transaction plan traced by an action code: open a pair at a buy while flat, close it at a sell while holding. -/ def decodePlan (n : Nat) (code : ActionCode n) : List (Nat × Nat) := (((List.finRange n).foldl (fun st i => match st.1 with | none => if code i = 1 then (some i.val, st.2) else st | some b => if code i = 2 then (none, st.2 ++ [(b, i.val)]) else st) ((none : Option Nat), ([] : List (Nat × Nat)))).2) /-- Boolean test for plan validity: every pair buys strictly before its in-bounds sell, and each sell precedes the next buy. -/ def validPlanB (prices : List Int) (plan : List (Nat × Nat)) : Bool := plan.all (fun p => decide (p.1 < p.2 ∧ p.2 < prices.length)) && (plan.zip plan.tail).all (fun q => decide (q.1.2 < q.2.1)) /-- Executable checker for `maxProfit_spec` over the finite action codes. -/ def maxProfit_check (input : Input) (result : Output) : Bool := decide ((∃ code : ActionCode input.1.length, validPlanB input.1 (decodePlan input.1.length code) = true ∧ planProfit input.1 input.2 (decodePlan input.1.length code) = result) ∧ (∀ code : ActionCode input.1.length, validPlanB input.1 (decodePlan input.1.length code) = true → planProfit input.1 input.2 (decodePlan input.1.length code) ≤ result)) theorem root_of_bridges (reflection : ∀ (prices : List Int) (plan : List (Nat × Nat)), validPlanB prices plan = true ↔ IsValidTransactionPlan prices plan) (coverage : ∀ (prices : List Int) (plan : List (Nat × Nat)), IsValidTransactionPlan prices plan → ∃ code : ActionCode prices.length, decodePlan prices.length code = plan) (input : Input) (result : Output) : maxProfit_check input result ↔ maxProfit_spec input result := by simp only [maxProfit_check, Bool.coe_iff_coe, decide_eq_true_eq, maxProfit_spec, IsGreatest, Set.mem_setOf_eq, upperBounds, reflection] constructor · rintro ⟨⟨code, hc, he⟩, hm⟩ refine ⟨⟨_, hc, he⟩, ?_⟩ rintro k ⟨plan, hp, rfl⟩ obtain ⟨code, rfl⟩ := coverage input.1 plan hp exact hm code hp · rintro ⟨⟨plan, hp, he⟩, hm⟩ obtain ⟨code, rfl⟩ := coverage input.1 plan hp exact ⟨⟨code, hp, he⟩, fun code hc => hm ⟨_, hc, rfl⟩⟩ theorem zip_tail_chain (plan : List (Nat × Nat)) : ((plan.zip plan.tail).all (fun q => decide (q.1.2 < q.2.1))) = true ↔ plan.Chain' (fun a b => a.2 < b.1) := by unfold List.Chain' induction plan with | nil => simp | cons a tail ih => cases tail 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 := a.2 < b.1)) ih theorem validPlanB_iff (prices : List Int) (plan : List (Nat × Nat)) : validPlanB prices plan = true ↔ IsValidTransactionPlan prices plan := by rw [validPlanB, Bool.and_eq_true, zip_tail_chain] simp only [List.all_eq_true, decide_eq_true_eq, IsValidTransactionPlan] theorem root_with_coverage (coverage : ∀ (prices : List Int) (plan : List (Nat × Nat)), IsValidTransactionPlan prices plan → ∃ code : ActionCode prices.length, decodePlan prices.length code = plan) (input : Input) (result : Output) : maxProfit_check input result ↔ maxProfit_spec input result := by exact root_of_bridges validPlanB_iff coverage input result def wxRun (n : Nat) (code : ActionCode n) : Option Nat × List (Nat × Nat) := (List.finRange n).foldl (fun st i => match st.1 with | none => if code i = 1 then (some i.val, st.2) else st | some b => if code i = 2 then (none, st.2 ++ [(b, i.val)]) else st) (none, []) def wxExtend {n : Nat} (code : ActionCode n) (a : Fin 3) : ActionCode (n+1) := fun i => if h : i.val < n then code ⟨i.val, h⟩ else a lemma wx_run_extend {n : Nat} (code : ActionCode n) (a : Fin 3) : wxRun (n+1) (wxExtend code a) = match (wxRun n code).1 with | none => if a = 1 then (some n, (wxRun n code).2) else wxRun n code | some b => if a = 2 then (none, (wxRun n code).2 ++ [(b,n)]) else wxRun n code := by have hm : ∀ (l : List (Fin n)) (st : Option Nat × List (Nat × Nat)), (l.map Fin.castSucc).foldl (fun st i => match st.1 with | none => if wxExtend code a i = 1 then (some i.val, st.2) else st | some b => if wxExtend code a i = 2 then (none, st.2 ++ [(b, i.val)]) else st) st = l.foldl (fun st i => match st.1 with | none => if code i = 1 then (some i.val, st.2) else st | some b => if code i = 2 then (none, st.2 ++ [(b, i.val)]) else st) st := by intro l st induction l generalizing st with | nil => rfl | cons i l ih => simp only [List.map_cons, List.foldl_cons] simp only [wxExtend, Fin.coe_castSucc, i.isLt, ↓reduceDIte] exact ih _ unfold wxRun rw [List.finRange_succ_last, List.foldl_append] rw [hm] simp [wxExtend] def wxReach (n : Nat) (st : Option Nat × List (Nat × Nat)) : Prop := ∃ code : ActionCode n, wxRun n code = st lemma wx_idle_succ {n : Nat} {st : Option Nat × List (Nat × Nat)} (h : wxReach n st) : wxReach (n+1) st := by rcases h with ⟨c, hc⟩ refine ⟨wxExtend c 0, ?_⟩ rw [wx_run_extend, hc] cases st.1 <;> simp lemma wx_buy_succ {n : Nat} {xs : List (Nat × Nat)} (h : wxReach n (none, xs)) : wxReach (n+1) (some n, xs) := by rcases h with ⟨c, hc⟩ refine ⟨wxExtend c 1, ?_⟩ rw [wx_run_extend, hc] simp lemma wx_sell_succ {n b : Nat} {xs : List (Nat × Nat)} (h : wxReach n (some b, xs)) : wxReach (n+1) (none, xs ++ [(b,n)]) := by rcases h with ⟨c, hc⟩ refine ⟨wxExtend c 2, ?_⟩ rw [wx_run_extend, hc] simp lemma wx_reach_mono {m n : Nat} {st : Option Nat × List (Nat × Nat)} (hmn : m ≤ n) (h : wxReach m st) : wxReach n st := by obtain ⟨d, rfl⟩ := Nat.exists_eq_add_of_le hmn induction d with | zero => simpa using h | succ d ih => simpa [Nat.add_assoc] using wx_idle_succ (ih (by omega)) lemma wx_pairwise_of_valid_chain (xs : List (Nat × Nat)) (hv : ∀ p ∈ xs, p.1 < p.2) (hc : xs.Chain' (fun a b => a.2 < b.1)) : xs.Pairwise (fun a b => a.2 < b.1) := by induction xs with | nil => simp | cons a xs ih => cases xs with | nil => simp | cons b bs => simp only [List.Chain', List.isChain_cons_cons] at hc have ht := ih (fun p hp => hv p (by simp [hp])) hc.2 refine List.Pairwise.cons ?_ ht intro c hcmem rcases List.mem_cons.mp hcmem with rfl | hcbs · exact hc.1 · have hbc : b.2 < c.1 := (List.pairwise_cons.mp ht).1 c hcbs have hb : b.1 < b.2 := hv b (by simp) omega lemma wx_reach_plan (plan : List (Nat × Nat)) (n : Nat) (hv : ∀ p ∈ plan, p.1 < p.2 ∧ p.2 < n) (hc : plan.Chain' (fun a b => a.2 < b.1)) : wxReach n (none, plan) := by induction plan using List.reverseRecOn generalizing n with | nil => exact wx_reach_mono (Nat.zero_le n) ⟨fun _ => 0, by simp [wxRun]⟩ | append_singleton xs p ih => have hp := hv p (by simp) have hcxs : xs.Chain' (fun a b => a.2 < b.1) := by exact (show (xs ++ [p]).Chain' _ from hc).left_of_append have hpw := wx_pairwise_of_valid_chain (xs ++ [p]) (fun q hq => (hv q hq).1) hc have hxb : ∀ q ∈ xs, q.2 < p.1 := by intro q hq exact (List.pairwise_append.mp hpw).2.2 q hq p (by simp) have hr0 : wxReach p.1 (none, xs) := ih p.1 (fun q hq => ⟨(hv q (by simp [hq])).1, hxb q hq⟩) hcxs have hr1 : wxReach (p.1+1) (some p.1, xs) := wx_buy_succ hr0 have hr2 : wxReach p.2 (some p.1, xs) := wx_reach_mono (by omega) hr1 have hr3 : wxReach (p.2+1) (none, xs ++ [(p.1,p.2)]) := wx_sell_succ hr2 exact wx_reach_mono (by omega) hr3 theorem decode_surjective (prices : List Int) (plan : List (Nat × Nat)) (h : IsValidTransactionPlan prices plan) : ∃ code : ActionCode prices.length, decodePlan prices.length code = plan := by have hr := wx_reach_plan plan prices.length h.1 h.2 rcases hr with ⟨code, hc⟩ exact ⟨code, by simpa [decodePlan, wxRun] using congrArg Prod.snd hc⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem maxProfit_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : maxProfit_check input result ↔ maxProfit_spec input result := by exact root_of_bridges validPlanB_iff decode_surjective input result /-! ### Implementation helpers -/ /-- One-day transition: from (cash, hold) and today's price, the updated (cash, hold) pair. -/ def cashHoldStep (fee : Int) (st : Int × Int) (price : Int) : Int × Int := (max st.1 (st.2 + price - fee), max st.2 (st.1 - price)) /-! ### Main algorithm (impl) -/ /-- Maximum profit by a two-state cash/hold dynamic program folded over the prices. -/ def maxProfitWithFee (input : Input) : Output := match input.1 with | [] => 0 | p :: rest => (rest.foldl (fun st price => cashHoldStep input.2 st price) (0, -p)).1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem maxProfitWithFee_correct (input : Input) (h : isValidInput input) : maxProfit_spec input (maxProfitWithFee input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 3, 2, 8, 4, 9], 2) #guard isValidInput ([1, 3, 7, 5, 10, 3], 3) #guard isValidInput ([1, 2, 3, 4, 5], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([], 0)) #guard !(isValidInput ([0], 0)) #guard !(isValidInput ([50000], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard maxProfit_check ([1, 3, 2, 8, 4, 9], 2) 8 #guard maxProfit_check ([1, 3, 7, 5, 10, 3], 3) 6 #guard maxProfit_check ([1, 2, 3, 4, 5], 1) 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(maxProfit_check ([1, 3, 2, 8, 4, 9], 2) 7) #guard !(maxProfit_check ([1, 3, 7, 5, 10, 3], 3) 7) #guard !(maxProfit_check ([1, 2, 3, 4, 5], 1) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard maxProfitWithFee ([1, 3, 2, 8, 4, 9], 2) == 8 #guard maxProfitWithFee ([1, 3, 7, 5, 10, 3], 3) == 6 #guard maxProfitWithFee ([1, 2, 3, 4, 5], 1) == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard maxProfit_check ([1, 3, 2, 8, 4, 9], 2) (maxProfitWithFee ([1, 3, 2, 8, 4, 9], 2)) #guard maxProfit_check ([1, 3, 7, 5, 10, 3], 3) (maxProfitWithFee ([1, 3, 7, 5, 10, 3], 3)) #guard maxProfit_check ([1, 2, 3, 4, 5], 1) (maxProfitWithFee ([1, 2, 3, 4, 5], 1)) end PBestTimeToBuyAndSellStockWithTransactionFee