Kadane's Algo

(i). Kadane's -Recursive

Python Code


def max_subarray_recursive(arr, n):
    if n == 1:
        return arr[0]
    
    max_ending_here = max_subarray_recursive(arr, n - 1)
    max_ending_here = max(arr[n - 1], max_ending_here + arr[n - 1])
    
    return max_ending_here

# Example usage
array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
n = len(array)
result = max_subarray_recursive(array, n)
print("Maximum Sum Subarray:", result)

(ii). Kadane's - Memoization(TOP DOWN)

Python Code


def max_subarray_top_down(arr, n, memo):
    if n == 1:
        return arr[0]
    
    if memo[n] != -1:
        return memo[n]
    
    max_ending_here = max(arr[n - 1], max_subarray_top_down(arr, n - 1, memo) + arr[n - 1])
    memo[n] = max_ending_here
    
    return max_ending_here

# Example usage
array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
n = len(array)
memo = [-1] * (n + 1)
result = max_subarray_top_down(array, n, memo)
print("Maximum Sum Subarray:", result)

(iii). Kadane's - Tabulation(Bottom UP)

Python Code


def max_subarray_bottom_up(arr):
    n = len(arr)
    max_ending_here = max_so_far = arr[0]
    
    for i in range(1, n):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)
    
    return max_so_far

# Example usage
array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
result = max_subarray_bottom_up(array)
print("Maximum Sum Subarray:", result)