Answer to Question #187029 in Python for ankitha

Question

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.

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

from sys import maxsize

def maxSubArraySum(l, n):
    max_so_far = -maxsize - 1
    max_ending_here = 0
    s = 0

    for i in range(0, n):

        max_ending_here += l[i]

        if max_so_far < max_ending_here:
            max_so_far = max_ending_here

        if max_ending_here < 0:
            max_ending_here = 0
            s = i + 1

    print("Maximum contiguous sum is %d" % (max_so_far))

if __name__ == '__main__':
    listA = [-2,-3,4,-1,-2,1,5,-3]
    maxSubArraySum(listA, len(listA))