"""
p09 — Maximum Subarray (Kadane's Algorithm)
===========================================
LeetCode 53 · Medium · Topics: Array, DP, Divide & Conquer

Sections:
  1. BRUTE FORCE — O(N^2) with running-sum trick (correctness oracle)
  2. KADANE — O(N) time, O(1) space (production)
  3. KADANE with explicit DP array — O(N) space (didactic)
  4. DIVIDE & CONQUER — O(N log N) (didactic / parallel-friendly form)
  5. STRESS TEST — all four implementations must agree
  6. EDGE CASES
"""

import random
from typing import List


# ----------------------------------------------------------------------
# 1. BRUTE FORCE — O(N^2) time
# ----------------------------------------------------------------------
def max_subarray_brute(nums: List[int]) -> int:
    n = len(nums)
    best = nums[0]
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s > best:
                best = s
    return best


# ----------------------------------------------------------------------
# 2. KADANE — O(N) time, O(1) space
# ----------------------------------------------------------------------
def max_subarray(nums: List[int]) -> int:
    # INVARIANT: at the top of iteration i,
    #   curr = max sum of any subarray ending exactly at index i-1
    #   best = max sum of any subarray ending at any index in 0..i-1
    # Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i])
    # The "max(nums[i], ...)" formulation (NOT "max(0, ...)") handles all-negative.
    curr = nums[0]
    best = nums[0]
    for i in range(1, len(nums)):
        x = nums[i]
        curr = x if x > curr + x else curr + x   # = max(x, curr + x)
        if curr > best:
            best = curr
    return best


# ----------------------------------------------------------------------
# 3. KADANE with explicit DP array — for didactic clarity
# ----------------------------------------------------------------------
def max_subarray_dp_array(nums: List[int]) -> int:
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    for i in range(1, n):
        dp[i] = max(nums[i], dp[i - 1] + nums[i])
    return max(dp)


# ----------------------------------------------------------------------
# 4. DIVIDE & CONQUER — O(N log N)
# ----------------------------------------------------------------------
def max_subarray_divide_conquer(nums: List[int]) -> int:
    def solve(lo: int, hi: int) -> int:
        if lo == hi:
            return nums[lo]
        mid = (lo + hi) // 2
        left_best = solve(lo, mid)
        right_best = solve(mid + 1, hi)
        # crossing — extend from mid leftward and from mid+1 rightward
        left_sum = nums[mid]
        s = 0
        for i in range(mid, lo - 1, -1):
            s += nums[i]
            if s > left_sum:
                left_sum = s
        right_sum = nums[mid + 1]
        s = 0
        for i in range(mid + 1, hi + 1):
            s += nums[i]
            if s > right_sum:
                right_sum = s
        cross = left_sum + right_sum
        return max(left_best, right_best, cross)

    return solve(0, len(nums) - 1)


# ----------------------------------------------------------------------
# 5. STRESS TEST
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000, max_n: int = 30) -> None:
    rng = random.Random(42)
    for it in range(iterations):
        n = rng.randint(1, max_n)
        # Mix in negatives heavily to expose the all-negative trap
        nums = [rng.randint(-50, 50) for _ in range(n)]
        # 10% chance: force all-negative
        if rng.random() < 0.1:
            nums = [-abs(x) - 1 for x in nums]
        a = max_subarray_brute(nums)
        b = max_subarray(nums)
        c = max_subarray_dp_array(nums)
        d = max_subarray_divide_conquer(nums)
        assert a == b == c == d, (
            f"disagreement on {nums}: brute={a} kadane={b} dp={c} dc={d}"
        )
    print(f"stress_test PASSED — {iterations} iterations (4 algorithms agree)")


# ----------------------------------------------------------------------
# 6. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases = [
        ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6, "canonical (LC example)"),
        ([1], 1, "single positive"),
        ([-1], -1, "single negative — the off-by-one trap"),
        ([-3, -2, -1, -5], -1, "all-negative — must NOT return 0"),
        ([5, 4, -1, 7, 8], 23, "mostly positive"),
        ([0, 0, 0], 0, "all zeros"),
        ([1, -100, 2, -100, 3], 3, "big negatives reset running sum"),
        ([1, 2, 3, 4, 5], 15, "all positive"),
    ]
    for nums, expected, label in cases:
        got = max_subarray(nums)
        status = "PASS" if got == expected else "FAIL"
        print(f"  [{status}] {label}: expected={expected} got={got}")


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