Python : 每日一题 35

ooxx7788

相信前两天看那么多字的题目已经烦了，今天看个简单的。

求出数列中和最大的切片的值。
例如[-2, 1, -3, 4, -1, 2, 1, -5, 4]中，[ 4, -1, 2, 1]的和最大为6,则返回 6
如果空列表，或者和为负，则返回0

1. test模块请找33,34题中。
   
2. test.assert_equals(maxSequence([]), 0)
   
3. test.assert_equals(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6)
   
4. test.assert_equals(maxSequence([-1, -1]), 0)
   
5. test.assert_equals(maxSequence(
   
6.     [-6, 21, -4, 19, -27, 22, -19, -27, 2, 20, -16, 26, 5, 13, -14, 22, -17, 23, -7, -8, 3, 26, -11, -28, 15, -21, -6,
   
7.      -22, 24, -2, -29, 28, 22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]), 84)

复制代码

我的代码如下：

游客，如果您要查看本帖隐藏内容请回复

ooxx7788

发完感觉好像和昨天的题目有点类型重复了，算了，就这样了。

哨子1122

思路

jerryxjr1220

这题可以用动态规划算法，这样只要1次循环就能得结果，而不需要循环中间套循环了。
思路就是先求局部最大值，再求全局最大值，而全局最大值必然是出自局部最大值中的。

1. longlist = [-6, 21, -4, 19, -27, 22, -19, -27, 2, 20, -16, 26, 5, 13, -14, 22, -17, 23, -7, -8, 3, 26, -11, -28, 15, -21, -6,
   
2.      -22, 24, -2, -29, 28, 22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]
   
3. 
   
4. def longchop(lst):
   
5.     local_max = global_max = -999999999
   
6.     for i in lst:
   
7.         local_max = max(i, local_max + i )
   
8.         global_max = max(global_max, local_max)
   
9.     return global_max
   
10. 
    
11. print (longchop(longlist))

复制代码

输出：
84

余欲渔

1. qp=lambda x:0 if a==[] or max(a)<=0 else max([sum(a[i:j]) for i in range(len(a)) for j in range(i+1,len(a)+1)])
   
2. a=[-2, 1, -3, 4, -1, 2, 1, -5, 4]
   
3. print(qp(a))

复制代码

余欲渔

jerryxjr1220 发表于 2017-4-27 21:20
这题可以用动态规划算法，这样只要1次循环就能得结果，而不需要循环中间套循环了。
思路就是先求局部最大 ...

这样确实一轮就结束

willLin

厉害了，jerry

solomonxian

我觉得以前不是这样想问题的，现在第一想法就是暴力破解

1. # 暴力破解，最后加上 [0] 是应对空列表或者全是负数的列表
   
2. def maxS(n):
   
3.     return max([sum(n[i:j]) for i in range(len(n)) for j in range(i+1,len(n)+1)]+[0])

复制代码

石小龙

1. list1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
   
2. x = sorted(list1)
   
3. print(x.pop())

复制代码

ooxx7788

石小龙 发表于 2017-11-21 16:46

显然你这个答案不能满足要求啊

编程新血

算法挠头......

shigure_takimi

1. def maxSequence(lst):
   
2.     if len(lst) == 0:
   
3.         print('空列表,返回0')
   
4.         return 0
   
5.     else:
   
6.         sequece = []
   
7.         maxSum = -float('inf')
   
8.         for i in range(len(lst)):
   
9.             for j in range(i+1, len(lst)+1):
   
10.                 if sum(lst[i:j]) >= maxSum:
    
11.                     maxSum = sum(lst[i:j])
    
12.                     if maxSum > 0:
    
13.                         sequece.append(lst[i:j])
    
14.         if maxSum < 0:
    
15.             print('最大切片和为负，返回0')
    
16.             return 0
    
17.         else:
    
18.             max_Seq = []
    
19.             for i in sequece:
    
20.                 if sum(i) == maxSum:
    
21.                     max_Seq.append(i)
    
22.             return maxSum,max_Seq   # 返回最大和及对应切片
    
23. 
    
24. list1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    
25. list2 = [-6, 21, -4, 19, -27, 22, -19, -27, 2, 20, -16, 26, 5, 13, -14, 22, \
    
26.          -17, 23, -7, -8, 3, 26, -11, -28, 15, -21, -6, -22, 24, -2, -29, 28, \
    
27.          22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]
    
28. list3 = []
    
29. list4 = [-1,-1,-1,-1]
    
30. list5 = [2,3,4,-1,-100,-1,4,3,2,0, -199, ]
    
31. 
    
32. print(maxSequence(list1))
    
33. print(maxSequence(list2))
    
34. print(maxSequence(list3))
    
35. print(maxSequence(list4))
    
36. print(maxSequence(list5))
    
37. 
    
38. 
    
39. #暴力破解
    
40. (6, [[4, -1, 2, 1]])
    
41. (84, [[17, 15, 23, 29]])
    
42. 空列表,返回0
    
43. 0
    
44. 最大切片和为负，返回0
    
45. 0
    
46. (9, [[2, 3, 4], [4, 3, 2], [4, 3, 2, 0]])

复制代码

shigure_takimi

1. def maxSequence(lst):
   
2.     if len(lst) == 0:
   
3.         print('空列表,返回0')
   
4.         return 0
   
5.     else:
   
6.         sequece = []
   
7.         maxSum = -float('inf')
   
8.         for i in range(len(lst)):
   
9.             for j in range(i+1, len(lst)+1):
   
10.                 if sum(lst[i:j]) >= maxSum:
    
11.                     maxSum = sum(lst[i:j])
    
12.                     if maxSum > 0:
    
13.                         sequece.append(lst[i:j])
    
14.         if maxSum < 0:
    
15.             print('最大切片和为负，返回0')
    
16.             return 0
    
17.         else:
    
18.             max_Seq = []
    
19.             for i in sequece:
    
20.                 if sum(i) == maxSum:
    
21.                     max_Seq.append(i)
    
22.             return maxSum,max_Seq   # 返回最大和及对应切片
    
23. 
    
24. list1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    
25. list2 = [-6, 21, -4, 19, -27, 22, -19, -27, 2, 20, -16, 26, 5, 13, -14, 22, \
    
26.          -17, 23, -7, -8, 3, 26, -11, -28, 15, -21, -6, -22, 24, -2, -29, 28, \
    
27.          22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]
    
28. list3 = []
    
29. list4 = [-1,-1,-1,-1]
    
30. list5 = [2,3,4,-1,-100,-1,4,3,2,0, -199, ]
    
31. 
    
32. print(maxSequence(list1))
    
33. print(maxSequence(list2))
    
34. print(maxSequence(list3))
    
35. print(maxSequence(list4))
    
36. print(maxSequence(list5))
    
37. 
    
38. ###
    
39. (6, [[4, -1, 2, 1]])
    
40. (84, [[17, 15, 23, 29]])
    
41. 空列表,返回0
    
42. 0
    
43. 最大切片和为负，返回0
    
44. 0
    
45. (9, [[2, 3, 4], [4, 3, 2], [4, 3, 2, 0]])
    
46. 
    
47. #  笨方法，本质上和楼上的solomonxian 的思路是一样的，不过solomonxian的+[0]很巧妙，一句代码也很简洁。
    
48. 
    
49. def maxS(n):
    
50.     return max([sum(n[i:j]) for i in range(len(n)) for j in range(i+1,len(n)+1)]+[0])
    
51. 
    
52. # 学习了

复制代码

yjsx86

看看

瞬秒爆加速

1. def fun(n):
   
2.     c=[0]
   
3.     for i in range(len(n)):
   
4.         for ii in range(i,len(n)+1):
   
5.             c = (sum(n[i:ii])>sum(c)) and n[i:ii] or c
   
6.     return c,sum(c)

复制代码

萧丹夜

还行

1. ## 代码
   
2. import test
   
3. 
   
4. def maxSequence(x):
   
5.     y = []
   
6.     if len(x) == 0:
   
7.         return 0
   
8.     else:
   
9.         for i in range(len(x)):
   
10.             y.append(x[i])
    
11.             result = x[i]
    
12.             for j in range(i+1,len(x)):
    
13.                 result += x[j]
    
14.                 y.append(result)
    
15.         return max(y)
    
16.    
    
17. ## 测试
    
18. test.assert_equals(maxSequence([]), 0)
    
19. test.assert_equals(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6)
    
20. test.assert_equals(maxSequence([-1, -1]), 0)
    
21. test.assert_equals(maxSequence(
    
22.     [-6, 21, -4, 19, -27, 22, -19, -27, 2, 20, -16, 26, 5, 13, -14, 22, -17, 23, -7, -8, 3, 26, -11, -28, 15, -21, -6,
    
23.      -22, 24, -2, -29, 28, 22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]), 84)
    
24. 
    
25. 
    
26. ## 结果
    
27. Success！
    
28. Success！
    
29. Fail!-1 not equals 0
    
30. 
    
31. Success！

复制代码

bjcce

ok

小强工作室

import itertools
def itertools_demo(x):
    list1=[]
    for i in range(len(x)):
        for j in itertools.accumulate(x[i:len(x)+1]):#运用模块迭代累加
            list1.append(j)
    print(max(list1))
if __name__=="__main__":
    longlist =[-6, 21, -4, 19, -27, 22, -19, -27, 2, 20, -16, 26, 5, 13, -14, 22, -17, 23, -7, -8, 3, 26, -11, -28, 15, -21, -6,-22, 24, -2, -29, 28, 22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]
    itertools_demo(longlist)

lyslyslys

xuexixuexi

算幽幽

I Love Fishc

1. def maxSequence(intarr):
   
2.     if intarr==[]:
   
3.         return 0
   
4.     return (max([sum (each)for each in [intarr[i:k] for i in range(len(intarr)) for k in range(i,len(intarr)+3)]]))

复制代码