Using Python, find the max subarray using recursion inversion method. The runtime should be O(n).

The max subarray uses either the last element or not:

MaxSubarray(a[1,...,n]) = max{MaxSubarray(a[1,...,n-1]), MaxSuffix(a[1,...,n])}

MaxSuffix(a[1,...n]) = max{0,MaxSuffix(a[1,...,n-1])+a[n]}

Dynamic Programming

1) MaxSubarray(a[1]) and MaxSuffix(a[1])

2) MaxSubarray(a[1,2]) and MaxSuffix(a[1,2])

3) MaxSubarray(a[1,2,3]) and MaxSuffix(a[1,2,3])

4) continued ...