Answer to Question #206071 in Python for Sudheer

Question

Summary

Code

DESCRIPTION

DISCUSS

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]

[2, -4, 5, -1, 2, -3]

[-4]

[-4, 5]

[-4, 5, -1]

[-4, 5, -1, 2]

[-4, 5, -1, 2, -3]

[5]

[5, -1]

[5, -1, 2]

[5, -1, 2, -3]

[-1]

[-1, 2]

[-1, 2, -3]

[2]

[2, -3]

[-3]

Among the above contiguous sub-lists, the contiguous sub-list [5, -1, 2] has the largest sum which is 6.

Answer 1

def maxSubArraySum(a,size):
     
    max_so_far = 0
    max_ending_here = 0
     
    for i in range(0, size):
        max_ending_here = max_ending_here + a[i]
        if max_ending_here < 0:
            max_ending_here = 0


        elif (max_so_far < max_ending_here):
            max_so_far = max_ending_here
             
    return max_so_far