import random
from kadane import kadane, kadane_with_indices, kadane_divide_conquer, max_subarray_circular


def brute(nums):
    if not nums:
        return 0
    best = nums[0]
    n = len(nums)
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s > best:
                best = s
    return best


cases = [
    [],
    [1],
    [-1],
    [5, -2, 3, -1, 4],
    [-2, -3, -1, -4],
    [1, 2, 3, 4],
    [-1, -2, 5, -1, 3],
    [0, 0, 0],
    [3, -4, 2, -1, 5, -3],
]

for c in cases:
    a = kadane(c)
    b = brute(c)
    assert a == b, (c, a, b)
    assert kadane_divide_conquer(c) == b, (c, "dc")

# indices check
s, idx = kadane_with_indices([5, -2, 3, -1, 4])
assert s == 9 and idx == (0, 4), (s, idx)
s, idx = kadane_with_indices([-2, -3, -1])
assert s == -1 and idx == (2, 2), (s, idx)
assert kadane_with_indices([]) == (0, None)

# randomized
rng = random.Random(42)
for _ in range(2000):
    n = rng.randint(0, 12)
    nums = [rng.randint(-6, 6) for _ in range(n)]
    assert kadane(nums) == brute(nums), nums
    assert kadane_divide_conquer(nums) == brute(nums), nums

# circular
assert max_subarray_circular([1, -2, 3, -2]) == 3
assert max_subarray_circular([5, -3, 5]) == 10
assert max_subarray_circular([-3, -2, -1]) == -1
assert max_subarray_circular([3, -1, 2, -1]) == 4
assert max_subarray_circular([1]) == 1

print("ALL TESTS PASS")