maxsum_subarray.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import os


def maxsum(arr):
    # maxsum, start, end:
    result = [arr[0], 0, 0]
    curr = [0, 0, 0]
    for i in range(0, len(arr)):
        s = arr[i] + curr[0]
        if s > result[0]:
            result[0] = s
            result[1] = curr[1]
            result[2] = i if s >= 0 else curr[2]

        if s >= 0:
            curr[0] = s
            curr[2] = i
        else:
            curr[0] = 0
            curr[1] = curr[2] = i + 1

    print('sum:%d,[%d:%d]' % (result[0], result[1], result[2])),
    print(arr[result[1]: result[2] + 1])
array = map(int, os.sys.argv[1:])
maxsum(array)