最大连续子序列和

 1 def findMaxSeq(s):
 2     # start,end are array indexes(indices) of the max subsequence
 3     start = 0
 4     end = 0
 5     # cur is the maximum sum of subsequence if s[i] is included, working accumulator
 6     cur = 0
 7     # maxSub is the maximum sum among all subsequences
 8     maxSub = 0
 9     for i in range(len(s)):
10         cur += s[i]
11         if (cur <= 0):
12             cur = 0
13             start = (i + 1) % len(s)
14         elif(maxSub < cur):
15             maxSub = cur
16             end = i
17     return maxSub, start, end
18 
19 def curRecords(seq):
20     # make a copy of the original sequence, otherwise original values will be changed, it is a reference.
21     s = seq[:]
22 
23     for i in range(1, len(s)):
24         # THE CURCIAL LOGIC
25         s[i] = max(s[i - 1] + s[i], s[i])
26     return s
27 
28 def line():
29     print("*************************************")
30 
31 def show(s):
32     print (s)
33     print (curRecords(s))
34     print (findMaxSeq(s))
35     line()
36 
37 # assuming sequences contain both positive and negative values
38 s1 = [3, -4, 8, -5, 0, 2, 6, -7, 6]
39 s2 = [-1, 3, 5, -2, 3, 0, -2, 9, -2, 3, -1]
40 s3 = [2, -2, 3, 2, 32, -5, -2, 8, -3, 11, 0, -11, -3, 5, -1]
41 s4 = [3, -4]
42 s5 = [-4, 3, 56, -15, 34, 0, -14, 4]
43 s6 = [-4, 3]
44 ss = [s1, s2, s3, s4, s5, s6]
45 line()
46 
47 for s in ss:
48     show(s)

*************************************
[3, -4, 8, -5, 0, 2, 6, -7, 6] 
[3, -1, 8, 3, 3, 5, 11, 4, 10]
(11, 2, 6)
*************************************
[-1, 3, 5, -2, 3, 0, -2, 9, -2, 3, -1]
[-1, 3, 8, 6, 9, 9, 7, 16, 14, 17, 16]
(17, 1, 9)
*************************************
[2, -2, 3, 2, 32, -5, -2, 8, -3, 11, 0, -11, -3, 5, -1]
[2, 0, 3, 5, 37, 32, 30, 38, 35, 46, 46, 35, 32, 37, 36]
(46, 2, 9)
*************************************
[3, -4]
[3, -1]
(3, 0, 0)
*************************************
[-4, 3, 56, -15, 34, 0, -14, 4]
[-4, 3, 59, 44, 78, 78, 64, 68]
(78, 1, 4)
*************************************
[-4, 3]
[-4, 3]
(3, 1, 1)
*************************************