[已解决]算法运行速度的问题，如何改进算法

火日羽

一个数组有 N 个元素，求连续子数组的最大和。 例如：[-1,2,1]，和最大的连续子数组为[2,1]，其和为 3
输入描述:
输入为两行。
第一行一个整数n(1 <= n <= 100000)，表示一共有n个元素
第二行为n个数，即每个元素,每个整数都在32位int范围内。以空格分隔。


输出描述:
所有连续子数组中和最大的值。

输入例子:
3
-1 2 1

输出例子:
3


程序：
def maxi(l,n,k,b):
   
    for i in range(n-k+1):
        b.append(sum(l[i:i+k]))
        
import sys
i=0
for line in sys.stdin:
    if line.strip()=='':
        break
    if i==0:
        n=int(line)
    else:
        l=line.split()
        l=[int(j) for j in l]
        b=[sum(l)]
        for s in range(1,n):
            maxi(l,n,s,b)
            
            
    i=i+1
print max(b)

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
case通过率为60.00%

最佳答案

月排行榜 / 总排行榜

jerryxjr1220

2017-3-28 12:46:25

计算子串的最大和：Kadane算法

1. def calc_max(a):
   
2.     b, max_sum = 0, -2147483648
   
3.     for i in range(len(a)):
   
4.         if b>0:
   
5.             b += a[i]
   
6.         else:
   
7.             b = a[i]
   
8.         if b > max_sum:
   
9.             max_sum = b
   
10.     return max_sum

复制代码

这个算法的时间复杂度是O（n）

跳转到最佳答案楼层

新手·ing

敢问阁下题从哪来
我也想做做

火日羽

新手·ing 发表于 2017-3-27 21:09
敢问阁下题从哪来
我也想做做

牛客网

jerryxjr1220

计算子串的最大和：Kadane算法

1. def calc_max(a):
   
2.     b, max_sum = 0, -2147483648
   
3.     for i in range(len(a)):
   
4.         if b>0:
   
5.             b += a[i]
   
6.         else:
   
7.             b = a[i]
   
8.         if b > max_sum:
   
9.             max_sum = b
   
10.     return max_sum

复制代码

这个算法的时间复杂度是O（n）

火日羽

jerryxjr1220 发表于 2017-3-28 12:46
计算子串的最大和：Kadane算法

这个算法的时间复杂度是O（n）

完美解答了我的问题 ， 受教了！ 非常感谢~