#!/usr/bin/python2.7

#File: maxChildSum.py

#Author: lxw

#Time: 2014-08-22

#Usage: Find the max sum of a sub-sequence in a sequence.

#NOTE:      @1: first, must be the max sum.

#           @2: if more than one sum is max(same max value), choose the longer sequence.

def main():

    #arr = [-12, 0, -14, -14, -13, -14, -2]  #"zero" test.

    #arr = [0, -14, -14, -13, -14, -2]  #another "zero" test.

    arr = [-100, -14, -14, -13, -14, -2]  #"all negtive" test.

    #arr = [-12, 10, 2, -14, -14, 13, -2]  #"longer sequence but not equal sum" test.

    #arr = [-12, 0, 10, -14, -14, -2]  #"as long as better" test.

    #arr = [-12, 0, 10, -14, -14, 3, 7, -2]  #"same sum & same length" test.

    #arr = [-12, 10, -14, -14, 3, 7, -2]  #"same sum but longer sequence" test.

    index = 0

    length = len(arr)

    while arr[index] < 0:

        index += 1

        if index == length:

            break

    if index < length:

        sum = -1    #This initial value is important.

        start = index

        temp_sum = 0    #sum

        temp_start = index

        end = 0

        while index < length:

            temp_sum += arr[index]

            if temp_sum >= 0:

                if temp_sum > sum:

                    sum = temp_sum

                    start = temp_start

                    end = index

                elif temp_sum == sum:

                    if start == temp_start:

                        end = index

                    elif index - temp_start > end - start:

                        start = temp_start

                        end = index

            else:

                temp_sum = 0

                temp_start = index + 1

            index += 1

        print "max sum:{0:<4}start:{1:<4}end:{2:<4}max length:{3:<4}".format(sum, start, end, end-start+1)

    else:

        #All the numbers are negative.

        print "max sum:{0:<4}start:{1:<4}end:{2:<4}max length:{3:<4}".format(0, 0, 0, 0)

if __name__ == '__main__':

    main()

else:

    print "Being imported as a module."