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

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

#! /usr/bin/env python#coding=utf-8def 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 maxVdef 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 maxAmaxArrayLog([-2,1,2,-41,-23,14,-23,-5,35,-3,63,-63,7,4,6])