<找工作 五> 子数组之和最大值
实现了两种，一种是算出最大值，一种是把最大值的子数组打印出来，时间复杂度都是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])?
