求子串累加的最大值

  1. # 求子串累加的最大值
  2. p = [1, -2, -2, 3,10,-4,7,2,-5]
  3. n = len(p)
  4. l = [0] * n
  5. for i in range(n):
  6.     mino = 0
  7.     j = i-1
  8.     while j>=0:
  9.         if p[j] < 0:
  10.             mino += p[j]
  11.             j -= 1
  12.         else:
  13.             break
  14.     e = p[i] + mino
  15.     if i > 0:
  16.         if e >= 0:
  17.             l[i] = l[i-1] + e
  18.         else:
  19.             l[i] = max(l[i-1], p[i])
  20.     else:
  21.         if p[i] > 0:
  22.             l[i] = p[i]
  23. ####################################################################################
  24. # 求子串累加的最大值
  25. p = [1,-5,1, 2,-2, 3,10,-4,7,2,-5]
  26. n = len(p)
  27. l = [0] * n
  28. for i in range(n): 
  29.     l[i] = max(l[i-1]+p[i], p[i])

最大上升子串

  1. # 最大上升子串
  2. p = [1, -2, -2, 3, 10, 4, 7]
  3. p2 = [1, -2, -1, 3, 10, -4, 7, 2, -5]
  4. p3 = [1, 4, 3, 2, 6, 7]
  6. def getdp2(arr):
  7.     n = len(arr)
  8.     dp = [0] * n
  9.     dp[0] = 1
  10.     l = [1]
  11.     if n > 1:
  12.         for i in range(1, n):
  13.             ma = 0
  14.             for j in range(i):
  15.                 if arr[i] > arr[j] and dp[j] + 1 > ma:
  16.                     ma = dp[j] + 1
  17.                 else:
  18.                     ma = 1
  19.             dp[i] = ma
  20.             print(dp)
  21.             l.append(max(dp))
  22.     print(l)
  23.     return dp
  25. dp = getdp2(p3)
  27. ##################################################################################
  28. # 最大上升子串
  29. p = [7, 1, 4, -2, 3, 6, 8, 10, 4, 7]
  30. n = len(p)
  31. l = [0] * n
  32. l[0] = 1
  33. x = []
  34. for i in range(n):
  35.     for j in range(i):
  36.         # print(j, i)
  37.         if p[j] < p[i]:
  38.             l[i] = l[j] + 1
  39.         else:
  40.             l[i] = 1
  41.         print(l, j, i)
  42.     x.append(max(l))
  43. print(x)

啥玩意啊

  1. #!/usr/bin/env python
  2. #-*- coding:utf-8 -*-
  3. p = [1,4,3,2,6,5]
  4. arr = [1,4,5,6,3,4,5,6,7]
  5. # n = len(p)
  6. # l2 = [0] * n
  7. # def getdp1(arr):
  8. #   for i in range(n):
  9. #       if i > 0:
  10. #           for j in range(i):
  11. #               if p[j] < p[i]:
  12. #                   l2[i] = max(1+l2[j], l2[i])
  13. #       else:
  14. #           l2[i] = 1
  15. # def getdp1(arr):
  16. #     n = len(arr)
  17. #     dp = [0] * n
  18. #     from ipdb import set_trace
  19. #     set_trace()
  20. #     for i in range(n):
  21. #         dp[i] = 1
  22. #         for j in range(i):
  23. #             if arr[i] > arr[j]:
  24. #                 dp[i] = max(dp[i], dp[j] + 1)
  25. def getdp1(arr):
  26.     n = len(arr)
  27.     dp = [0] * n
  28.     for i in range(n):
  29.         dp[i] = 1
  30.         for j in range(i):
  31.             if arr[i] > arr[j]:
  32.                 dp[i] = max(dp[i], dp[j] + 1)
  33.     return dp
  34. c = getdp1(arr)