题目：给定数组a[1…n]，求最大子数组和，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大。

思路：遍历一遍进行累加sum, 申请变量ans保存当前最大值，如果sum<0时候进行清空，这样，ans总是可以保持最大。
时间复杂度为O(n)
如果全负数的输入，直接返回最大的一个值即可

# 给定数组a[1…n]，求最大连续子数组和，即找出1<=i<=j<=n，使a[i]+a[i+1]+…+a[j]最大

class MaxSum(object):
    def __init__(self, init_list):
        self.l = init_list
        self.subl = []

    def max_sum(self):
        sum = 0
        ans = 0

        if max(self.l) < 0:
            return max(self.l)

        for x in self.l:
            sum += x
            ans = sum if sum > ans else ans
            print 'x:%s, sum:%s  ans:%s'%(x, sum,ans)
            if sum < 0: sum = 0

        return ans

if __name__ == '__main__':
    test=[-1, -1,-5,-5,-1,-33,-10]
    n = MaxSum(test)
    print n.max_sum()