<找工作 5> 子数组之和最大值

<找工作 五> 子数组之和最大值

实现了两种，一种是算出最大值，一种是把最大值的子数组打印出来，时间复杂度都是o(n)，空间复杂度o(1)

#! /usr/bin/env python
#coding=utf-8
def maxArray(a):
    print sum(a)
    maxV=a[-1]
    tempV=a[-1]
    for i in xrange(len(a)-2,-1,-1):
        tempV=max([a[i],tempV+a[i]])
        maxV=max([maxV,tempV])
    print maxV

def maxArrayLog(a):
    #print sum(a)
    maxV=a[-1]
    maxA=[a[-1]]
    tempV=a[-1]
    tempA=[a[-1]]
    for i in xrange(len(a)-2,-1,-1):
        if a[i]>tempV+a[i]:
            tempV=a[i]
            tempA=[]
        else:
            
            tempV+=a[i]
        tempA.append(a[i])
        if maxV<tempV:
            maxV=tempV
            maxA=list(tempA)
    maxA.reverse()
    print maxV
    print maxA


maxArrayLog([-2,1,2,-41,-23,14,-23,-5,35,-3,63,-63,7,4,6])