Program 9: Apply optimization techniques to find the maximum value in a list.

def find_maximum(data):
    if not data:
        raise ValueError("List is empty")

    # Method 1: Optimal Linear Scan (O(n))
    max_linear = data[0]
    for value in data[1:]:
        if value > max_linear:
            max_linear = value

    # Method 2: Divide and Conquer (O(n))
    def max_divide_conquer(arr, left, right):
        if left == right:
            return arr[left]

        mid = (left + right) // 2
        return max(
            max_divide_conquer(arr, left, mid),
            max_divide_conquer(arr, mid + 1, right)
        )

    max_dc = max_divide_conquer(data, 0, len(data) - 1)

    return max_linear, max_dc


print("Optimization - Find Maximum:")

data = [3, 7, 2, 9, 1, 5, 8, 4]
max_lin, max_dc = find_maximum(data)

print(f"Maximum (Linear): {max_lin}")
print(f"Maximum (Divide & Conquer): {max_dc}")

import timeit

def find_maximum(data):
    if not data:
        raise ValueError("List is empty")

    # Linear Scan
    max_linear = data[0]
    for value in data[1:]:
        if value > max_linear:
            max_linear = value

    # Divide and Conquer
    def max_divide_conquer(arr, left, right):
        if left == right:
            return arr[left]
        mid = (left + right) // 2
        return max(
            max_divide_conquer(arr, left, mid),
            max_divide_conquer(arr, mid + 1, right)
        )

    max_dc = max_divide_conquer(data, 0, len(data) - 1)
    return max_linear, max_dc


# ---- Computational Efficiency (Time + Space) ----
def computational_efficiency(data):
    n = len(data)

    linear_time = timeit.timeit(lambda: max(data), number=1)
    dc_time = timeit.timeit(lambda: find_maximum(data)[1], number=1)

    return {
        "linear": {
            "time": linear_time,
            "space": "O(1)",
            "comparisons": n - 1
        },
        "divide_conquer": {
            "time": dc_time,
            "space": "O(log n)",
            "comparisons": n - 1
        }
    }


# ---------------- Driver Code ----------------
print("Optimization - Find Maximum")

data = [3, 7, 2, 9, 1, 5, 8, 4]

max_lin, max_dc = find_maximum(data)
eff = computational_efficiency(data)

print(f"\nMaximum (Linear): {max_lin}")
print(f"Maximum (Divide & Conquer): {max_dc}")

print("\nComputational Efficiency:")

print("Linear Scan")
print(" Time:", f"{eff['linear']['time']:.8f}s")
print(" Space:", eff['linear']['space'])
print(" Comparisons:", eff['linear']['comparisons'])

print("\nDivide & Conquer")
print(" Time:", f"{eff['divide_conquer']['time']:.8f}s")
print(" Space:", eff['divide_conquer']['space'])
print(" Comparisons:", eff['divide_conquer']['comparisons'])