"""
p03 — Best Time to Buy and Sell Stock
=====================================
LeetCode 121 · Easy · Topics: Array, DP, Greedy
"""

import random
from typing import List


# ----------------------------------------------------------------------
# 1. BRUTE FORCE — O(N^2) all pairs
# ----------------------------------------------------------------------
def max_profit_brute(prices: List[int]) -> int:
    best = 0
    n = len(prices)
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, prices[j] - prices[i])
    return best


# ----------------------------------------------------------------------
# 2. OPTIMAL — running min + per-step profit. O(N) time, O(1) space.
# ----------------------------------------------------------------------
def max_profit(prices: List[int]) -> int:
    # INVARIANT: at iteration i, `min_so_far` = min(prices[0..i-1]) BEFORE the update,
    # so `price - min_so_far` is the profit if we sell today using the best historical buy.
    # ORDER MATTERS: compute profit BEFORE updating min, else we allow buy=sell same day.
    min_so_far = float("inf")
    best = 0
    for price in prices:
        best = max(best, price - min_so_far)
        min_so_far = min(min_so_far, price)
    return best


# ----------------------------------------------------------------------
# 3. ALTERNATE OPTIMAL — Kadane's on consecutive diffs (didactic equivalence)
# ----------------------------------------------------------------------
def max_profit_kadane(prices: List[int]) -> int:
    if len(prices) < 2:
        return 0
    cur = best = 0
    for i in range(1, len(prices)):
        cur = max(0, cur + prices[i] - prices[i - 1])
        best = max(best, cur)
    return best


# ----------------------------------------------------------------------
# 4. STRESS TEST — all three must agree
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 50) -> None:
    rng = random.Random(42)
    for _ in range(iterations):
        n = rng.randint(0, max_n)
        prices = [rng.randint(-20, 100) for _ in range(n)]  # negatives test sign handling
        a = max_profit_brute(prices)
        b = max_profit(prices)
        c = max_profit_kadane(prices)
        assert a == b == c, f"disagree on {prices}: brute={a}, optimal={b}, kadane={c}"
    print(f"stress_test PASSED — {iterations} iterations (3 algorithms agree)")


# ----------------------------------------------------------------------
# 5. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([7, 1, 5, 3, 6, 4], 5, "canonical: buy 1 sell 6"),
        ([7, 6, 4, 3, 1], 0, "monotonic decrease — no profit possible"),
        ([1], 0, "single price — no transaction possible"),
        ([], 0, "empty"),
        ([2, 4, 1], 2, "trap: don't buy at last-day min"),
        ([1, 2, 3, 4, 5], 4, "monotonic increase"),
        ([3, 3, 3, 3], 0, "all equal — 0 profit"),
    ]
    for prices, expected, label in cases:
        actual = max_profit(prices)
        status = "PASS" if actual == expected else "FAIL"
        print(f"  [{status}] {label}: prices={prices} → {actual} (expected {expected})")


if __name__ == "__main__":
    print("=== Edge cases ===")
    edge_cases()
    print("\n=== Stress test ===")
    stress_test()