Python : 每日一题 35

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

求出数列中和最大的切片的值。
例如[-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)

我的代码如下：

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

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([sum(a[i:j]) 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次循环就能得结果，而不需要循环中间套循环了。
思路就是先求局部最大 ...

这样确实一轮就结束

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

厉害了，jerry

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

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

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

石小龙 · 发表于 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[i:j]) >= maxSum:
                    maxSum = sum(lst[i:j])
                    if maxSum > 0:
                        sequece.append(lst[i:j])
        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 = [2,3,4,-1,-100,-1,4,3,2,0, -199, ]

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


#暴力破解
(6, [[4, -1, 2, 1]])
(84, [[17, 15, 23, 29]])
空列表,返回0
0
最大切片和为负，返回0
0
(9, [[2, 3, 4], [4, 3, 2], [4, 3, 2, 0]])

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[i:j]) >= maxSum:
                    maxSum = sum(lst[i:j])
                    if maxSum > 0:
                        sequece.append(lst[i:j])
        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 = [2,3,4,-1,-100,-1,4,3,2,0, -199, ]

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

###
(6, [[4, -1, 2, 1]])
(84, [[17, 15, 23, 29]])
空列表,返回0
0
最大切片和为负，返回0
0
(9, [[2, 3, 4], [4, 3, 2], [4, 3, 2, 0]])

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

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

# 学习了

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

看看

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

def fun(n):
    c=[0]
    for i in range(len(n)):
        for ii in range(i,len(n)+1):
            c = (sum(n[i:ii])>sum(c)) and n[i:ii] 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[i])
            result = x[i]
            for j in range(i+1,len(x)):
                result += x[j]
                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[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 · 发表于 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([sum (each)for each in [intarr[i:k] for i in range(len(intarr)) for k in range(i,len(intarr)+3)]]))

账号		自动登录	找回密码
密码			立即注册

[技术交流] Python : 每日一题 35

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐: