算法题：最大子段和

千年沉寂

给定由n个整数组成的系列a1,a2,a3,...,an,求该序列的子段和的最大值。当所以整数均为负整数时定义最大子段和为0。
例如序列[-2,11,-4,13,-5,-2]的最大子段和为20.

victorlee129

动态规划之
f(x)=max{data(x),f(x-1)+data(x)}
ans=max{f(x),for x in 1..n}
代码：

1. 
   
2. data=input();
   
3. f=[0]*(len(data)+1);
   
4. for i in xrange(1,len(data)+1) :
   
5.   f[i]=((f[i-1]+data[i-1])>data[i-1])and (f[i-1]+data[i-1])or data[i-1];
   
6. print max(f);
   

复制代码

daybreakcx

data=[-2,11,-4,13,-5,-2] res=0 curr=0 for i in range(len(data)):     curr=max(0,curr+data[i])     res=max(res,curr) print(res)

来晚了，附上代码

niexining

好算法！学习了。

julyzergcn

import collections a = [-2,11,-4,13,-5,-2] dic = collections.defaultdict(list) for i in range(len(a)):     for j in range(len(a), i, -1):         dic[sum(a[i:j])].append(a[i:j]) for k,v in dic.items():     print k,'-',v print 'the maximum subsegment is:' lst = dic.keys() print max(lst),'-',dic[max(lst)]

>pythonw -u "b.py" 2 - [[-4, 13, -5, -2]] 4 - [[-4, 13, -5]] 5 - [[-2, 11, -4]] 6 - [[13, -5, -2]] 7 - [[11, -4]] 8 - [[13, -5]] 9 - [[-2, 11], [-4, 13]] 11 - [[-2, 11, -4, 13, -5, -2], [11]] 13 - [[-2, 11, -4, 13, -5], [11, -4, 13, -5, -2], [13]] 15 - [[11, -4, 13, -5]] 18 - [[-2, 11, -4, 13]] 20 - [[11, -4, 13]] -7 - [[-5, -2]] -5 - [[-5]] -4 - [[-4]] -2 - [[-2], [-2]] the maximum subsegment is: 20 - [[11, -4, 13]] >Exit code: 0

julyzergcn

import collections a = [-2,11,-4,13,-5,-2] dic = collections.defaultdict(list) for i in range(len(a)):     for j in range(len(a), i, -1):         dic[sum(a[i:j])].append(a[i:j]) for k,v in dic.items():     print k,'-',v print 'the maximum subsegment is:' lst = dic.keys() print max(lst),'-',dic[max(lst)]

>pythonw -u "b.py" 2 - [[-4, 13, -5, -2]] 4 - [[-4, 13, -5]] 5 - [[-2, 11, -4]] 6 - [[13, -5, -2]] 7 - [[11, -4]] 8 - [[13, -5]] 9 - [[-2, 11], [-4, 13]] 11 - [[-2, 11, -4, 13, -5, -2], [11]] 13 - [[-2, 11, -4, 13, -5], [11, -4, 13, -5, -2], [13]] 15 - [[11, -4, 13, -5]] 18 - [[-2, 11, -4, 13]] 20 - [[11, -4, 13]] -7 - [[-5, -2]] -5 - [[-5]] -4 - [[-4]] -2 - [[-2], [-2]] the maximum subsegment is: 20 - [[11, -4, 13]] >Exit code: 0

teebye

这个算法好

teebye

data=[-2,11,-4,13,-5,-2]    result = 0  sum = 0 0.upto(data.size-1) { |i|         if sum>0         sum+=data[i]     else         sum = data[i]     end     result = sum if sum>result } p result

千年沉寂

这个算法有很多种实现，复杂度不一样。采用动态规划复杂度为O(n),算法效率最高

yjphhw

不太理解，，，慢慢学习。。