Answer to Question #173936 in Python for phani

Question

Max Contiguous Subarray
Given a list of integers, write a program to identify the contiguous sub-list that has the largest sum and print the sum. Any non-empty slice of the list with step size 1 can be considered as a contiguous sub-list.
Input
The input will contain space-separated integers, denoting the elements of the list.
Output
The output should be an integer.
Explanation
For example, if the given list is [2, -4, 5, -1, 2, -3], then all the possible contiguous sub-lists will be,
[2]
[2, -4]
[2, -4, 5]
[2, -4, 5, -1]
[2, -4, 5, -1, 2]
[-4]
[-4, 5]
[-4, 5, -1]
[-4, 5, -1, 2]
[5]
[5, -1]
[5, -1, 2]
[-1]
[-1, 2]
[2]
Among the above contiguous sub-lists, the contiguous sub-list [5, -1, 2] has the largest sum which is 6.
Sample Input 1
2 -4 5 -1 2 -3
Sample Output 1
6
Sample Input 2
-2 -3 4 -1 -2 1 5 -3
Sample Output 2
7

Answer 1

# use the Kadane Algorithm
def max_subarray(numbers):
    max_sum = float('-inf')
    current_sum = 0
    for number  in numbers:
        current_sum = max(0, current_sum + number)
        max_sum = max(number, current_sum + number)
    return max_sum

def main():
    numbers_str = input("Enter the list items on one line separated by a space")
    numbers = numbers_str.split()
    numbers = [float(item) for item in numbers]
    max_sum = max_subarray(numbers)
    print(f'Max Contiguous Subarray {max_sum}')
    
if __name__ == "__main__":
    main()