2.求一个数组有最大和的子串

'''问题是一个数组比如[3,-2,6,8],求他的一个子串,st这个子串的sum最大''''''经典动态规划问题,也就是一直保持更新,核心就是这个更新函数的写法''''''思路就是:先上来把3作为最好的sum,然后对他进行更新,更新的原则是,如果当前sum大于0,那么他对于后面的加项的提升还是有作用的,所以继续扩充子串,否则就扔掉这个子串,直接把他后面的当成子串第一个,继续更新显然算法O(N)的复杂度.'''a=[0,-2032432432,1243432,68689,645,-45,-343545,-999999992,399999,-9999,9898]import randoma=list(range(-11,10,3))random.shuffle(a)print (a)#下面开始动态规划daan=he=a[0]left=0right=0#left,right标示从index left 加到index right包含index rightfor i in range(1,len(a)):      if he+a[i]<0:            if i+1
      
       daan:                  daan=he                  want_left=left                  want_right=rightprint (daan,want_left,want_right,sum(a[want_left:want_right+1]))
      

 3.该写最大子序列的和了

'''首先复习,子序列和子串的区别.子序列就是一个按照原顺序 排列的子集合,每个元素的原地址可以不连续而子串每个元素的原地址必须连续'''a=[1,23,45,6,8,78,89,89,999,-342,-34,-67]#首先是拥有最大子序列的和的子序列:这个答案,显然是提取所有的正数组成的序列即可#然后问题改成:'''需要求最长的上升子序列的长度和坐标位置''''''比如a=[1,2,5,3,4]  分析,开始从1,2,5取到了没问题,下面的3该如何选取?因为3比5小比2大,所以把原来子序列里面的5换成3是一种根据贪心来说更好的选择.那么如果a=[1,2,5,1.5,1.6,1.7]or a=[1,2,5,1.5],那么如何选择?这里面选2还是选1.5就很麻烦了.''''''这里面北大的一个算法课程讲过,需要考虑这样一个数组b,b[i]标示以a[i]为结尾的最长上升子序列的长度.好反向的思考方式.继续分析前面的比如a=[1,2,5,1.5,1.6,1.7],那么b=[1,2,3,2,3,4],所以答案是4,问题是如何获得这个b数组,继续动态规划.b[0]显然,b[1]也显然,假设b[0]到b[i]都知道了,那么b[i+1]该如何得到?动态规划思想好像数学归纳法.当然类似数学里面的方法从低角标开始尝试就知道了''''''b[0],b[1]已知,那么b[2]是多少,考虑问题转化成应该把5接到b[0]为结尾的子序列,还是b[1]为结尾的子序列,或者他自己成为一个子序列,来似的得到的子序列最长.1.首先判断是否能接,把5跟1比跟2比都大,所以他都能接到a[0]结尾的子序列,和a[1]结尾的子序列里面,所以b[2]=max(b[0]+1,b[1]+1,1)即可.思路get下面直接写代码即可'''import randoma=list(range(1,10))random.shuffle(a)  #注意shuffle是一个工厂函数,不需要再赋值了.ps:突然想到的学算法的体会:#尽量不要看别人的代码,只学习别人的大体思路,然后自己写code,学的才扎实,类似数学做题,老看别人的解答没啥大用,#看看别人的思路,然后自己从头到尾写一次就能学到不少.print (a)#首先建立数组b,也是这个问题的本质.b=[1]*len(a)for i in range(len(a)):      k=[]#k用来储存a[i]能拼接的index      for j in range(i):#这个for来找k            if a[j]

 4.上升子串

'''最长不严格上升子串问题''''''a=[2,4,-1,6,7,8],显然长度是4,感觉好废话,直接扫描即可''''''直接代码'''import randoma=list(range(10))random.shuffle(a)print (a)require_left=left=0require_right=right=0he=1for i in range(len(a)):      if i==0:            continue      else:            if a[i]>=a[i-1]:                  right+=1                                    tmp=len(a[left:right+1])                                 if (tmp>he):                        he=tmp                        require_left=left                        require_right=right            else:                  left=i                  right=i               print (he,end=''),print ('是长度')print (require_left,end=''),print('是开始index')print (require_right,end=''),print('是结尾index')print('具体的数是',end=''),print (a[require_left:require_right+1])print('下面是其他东西')#如何python 打印不回车,加一个end参数就行了.print('3432423', end=""),print (3432423)

 5.用单链表实现栈和队列

'''算法导论中文本p134''''''1.用一个单链表来实现一个栈,要求操作push和pop的运行时间仍为O(1)''''''发现了一个很吊的东西叫windows api,利用里面函数可以控制windows.实现非常多的操作'''class node():      def __init__(self,a):#另外python也可以在类里面定义类.类里面的属性可                            #以定义成类的属性或者实例的属性.                       self.data=a           self.next=Noneclass link():            def __init__(self):            self.head=node(None)  #需要逆着做链表.比如8本书摞起来放,最上面的书是head,倒数第二上面                                        #的是head.next....这样做链表才行.                  def push(self,a):         #保证head一直指向栈顶元素.                              e=node(a)                  e.next=self.head                  self.head=e                        def pop(self):                        if self.head.next==None:                  print ('error')                  return             else:                  re=self.head.data  #保证head一直指向栈顶元素.                  self.head=self.head.next                  print (re)                  return reb=link();    b.push(3)  #用分号可以把两句化拼成一句话,节省代码长度.b.push(4)b.push(5)b.push(6)b.pop()b.pop()b.pop()b.pop()b.pop()b.pop()  #还是成功了哈.class node():      def __init__(self,a):#另外python也可以在类里面定义类.类里面的属性可                            #以定义成类的属性或者实例的属性.                       self.data=a           self.next=None'''用一个单链表来实现一个队列,要求操作enqueue和dequeue的运行时间是O(1)'''class queue():      def __init__(self):            self.head=node(None)        #注意这里面开始时候head和tail都不是真正的元素,都是哨兵.            self.tail=node(None)            self.head.next=self.tail      def push(self,a):         #保证head一直指向栈顶元素.                              e=node(a)                  if self.head.next.data==None:                      self.head.next=e                  self.tail.next=e                  self.tail=e    #现在tail指向最后一个      def pop(self):            if self.head==None:                print ('error')                return            if self.head.data==None and self.head.next==None:                print ('error')                return            if self.head.data==None and self.head.next.data!=None:                  self.head=self.head.next                        re=self.head.data            print (re)            self.head=self.head.nexta=queue()a.push(3)a.push(4)a.push(5)a.push(5)a.pop()a.pop()a.pop()a.pop()a.pop()a.pop()a.pop()