Answer to Question #283001 in Python for Raju

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

def max_subarray(a):
    best_sum = 0
    curr_sum = 0


    for x in a:
        curr_sum = max(0, curr_sum+x)
        best_sum = max(best_sum, curr_sum)
         
    return best_sum


def main():
    line = input()
    a = [int(s) for s in line.split()]
    best_sum = max_subarray(a)
    print(best_sum)



if __name__ == '__main__':
    main()