Python : 每日一题 35,Python交流,技术交流,鱼C论坛

ooxx7788 发表于 2017-4-27 13:53:46

Python : 每日一题 35

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

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

test模块请找33,34题中。
test.assert_equals(maxSequence([]), 0)
test.assert_equals(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6)
test.assert_equals(maxSequence([-1, -1]), 0)
test.assert_equals(maxSequence(
[-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]), 84)

我的代码如下：
**** Hidden Message *****

ooxx7788 发表于 2017-4-27 13:58:44

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

哨子1122 发表于 2017-4-27 16:25:00

思路

jerryxjr1220 发表于 2017-4-27 21:20:39

本帖最后由 jerryxjr1220 于 2017-4-27 21:21 编辑

这题可以用动态规划算法，这样只要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,
-22, 24, -2, -29, 28, 22, -6, 17, 4, -29, 3, 8, 2, -18, -1, -9, -23, 9, -18, 17, 15, 23, 29]

def longchop(lst):
local_max = global_max = -999999999
for i in lst:
local_max = max(i, local_max + i )
global_max = max(global_max, local_max)
return global_max

print (longchop(longlist))

输出：
84

余欲渔 发表于 2017-4-28 21:25:34

本帖最后由余欲渔于 2017-4-28 21:33 编辑

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

余欲渔 发表于 2017-4-28 21:39:02

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

这样确实一轮就结束{:5_106:}

willLin 发表于 2017-5-13 21:20:05

厉害了，jerry

solomonxian 发表于 2017-6-22 21:09:09

我觉得以前不是这样想问题的，现在第一想法就是暴力破解{:10_250:}
# 暴力破解，最后加上是应对空列表或者全是负数的列表
def maxS(n):
return max() for i in range(len(n)) for j in range(i+1,len(n)+1)]+)

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

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

ooxx7788 发表于 2017-11-21 16:47:42

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

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

编程新血 发表于 2017-11-27 19:40:11

算法挠头......

shigure_takimi 发表于 2017-12-1 20:43:27

def maxSequence(lst):
if len(lst) == 0:
   print('空列表,返回0')
   return 0
else:
   sequece = []
   maxSum = -float('inf')
   for i in range(len(lst)):
         for j in range(i+1, len(lst)+1):
            if sum(lst) >= maxSum:
               maxSum = sum(lst)
               if maxSum > 0:
                     sequece.append(lst)
   if maxSum < 0:
         print('最大切片和为负，返回0')
         return 0
   else:
         max_Seq = []
         for i in sequece:
            if sum(i) == maxSum:
               max_Seq.append(i)
         return maxSum,max_Seq # 返回最大和及对应切片

list1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
list2 = [-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]
list3 = []
list4 = [-1,-1,-1,-1]
list5 =

print(maxSequence(list1))
print(maxSequence(list2))
print(maxSequence(list3))
print(maxSequence(list4))
print(maxSequence(list5))

#暴力破解
(6, [])
(84, [])
空列表,返回0
0
最大切片和为负，返回0
0
(9, [, , ])

shigure_takimi 发表于 2017-12-1 20:48:46

def maxSequence(lst):
if len(lst) == 0:
   print('空列表,返回0')
   return 0
else:
   sequece = []
   maxSum = -float('inf')
   for i in range(len(lst)):
         for j in range(i+1, len(lst)+1):
            if sum(lst) >= maxSum:
               maxSum = sum(lst)
               if maxSum > 0:
                     sequece.append(lst)
   if maxSum < 0:
         print('最大切片和为负，返回0')
         return 0
   else:
         max_Seq = []
         for i in sequece:
            if sum(i) == maxSum:
               max_Seq.append(i)
         return maxSum,max_Seq # 返回最大和及对应切片

list1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
list2 = [-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]
list3 = []
list4 = [-1,-1,-1,-1]
list5 =

print(maxSequence(list1))
print(maxSequence(list2))
print(maxSequence(list3))
print(maxSequence(list4))
print(maxSequence(list5))

###
(6, [])
(84, [])
空列表,返回0
0
最大切片和为负，返回0
0
(9, [, , ])

#笨方法，本质上和楼上的solomonxian 的思路是一样的，不过solomonxian的+很巧妙，一句代码也很简洁。

def maxS(n):
return max() for i in range(len(n)) for j in range(i+1,len(n)+1)]+)

# 学习了

yjsx86 发表于 2017-12-1 22:41:39

看看

瞬秒爆加速 发表于 2018-3-12 15:08:26

def fun(n):
c=
for i in range(len(n)):
for ii in range(i,len(n)+1):
c = (sum(n)>sum(c)) and n or c
return c,sum(c)

萧丹夜 发表于 2018-5-27 15:33:09

还行
## 代码
import test

def maxSequence(x):
y = []
if len(x) == 0:
   return 0
else:
   for i in range(len(x)):
         y.append(x)
         result = x
         for j in range(i+1,len(x)):
            result += x
            y.append(result)
   return max(y)

## 测试
test.assert_equals(maxSequence([]), 0)
test.assert_equals(maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4]), 6)
test.assert_equals(maxSequence([-1, -1]), 0)
test.assert_equals(maxSequence(
[-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]), 84)

## 结果
Success！
Success！
Fail!-1 not equals 0

Success！

bjcce 发表于 2018-5-28 21:18:12

小强工作室 发表于 2018-7-18 14:43:40

本帖最后由小强工作室于 2018-7-18 16:50 编辑

import itertools
def itertools_demo(x):
list1=[]
for i in range(len(x)):
for j in itertools.accumulate(x):#运用模块迭代累加
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 发表于 2018-9-27 16:41:14

xuexixuexi

算幽幽 发表于 2018-9-29 11:37:17

I Love Fishc def maxSequence(intarr):
if intarr==[]:
return 0
return (max( for i in range(len(intarr)) for k in range(i,len(intarr)+3)]]))

页: [1] 2

鱼C论坛's Archiver

Python : 每日一题 35