最大子串和

好吧，这个题目已经滥大街了，不过还是很有意思的。

复杂的解法容易想到，O(n)的则需要一些思考。

关键在于想明白，在遍历这个序列时，如何记录当前元素之前的最大子串和，加入当前元素后应该如何更新最大子串和。

正好python练练手

 1 def findMaxStr(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
 6     # accumulator
 7     cur = s[0]
 8     # maxSub is the maximum sum among all subsequences
 9     maxSub = s[0]
10     for i in range(1, len(s)):
11         cur += s[i]
12         if (cur <= s[i]):
13             cur = s[i]
14             if(s[i] > 0):
15                 start = i
16             if(s[i] > maxSub):
17                 start = i
18                 end = i
19         if(maxSub < cur):
20             maxSub = cur
21             end = i
22     return maxSub, start, end
23 
24 
25 def curRecords(seq):
26     # make a copy of the original sequence, otherwise original values will be
27     # changed, it is a reference.
28     s = seq[:]
29 
30     for i in range(1, len(s)):
31         # THE CRUCIAL LOGIC
32         s[i] = max(s[i - 1] + s[i], s[i])
33     return s
34 
35 
36 def line():
37     print("*************************************")
38 
39 
40 def show(s):
41     print (s)
42     print (curRecords(s))
43     print (findMaxStr(s))
44     line()
45 
46 # assuming sequences contain both positive and negative values
47 # Not assuming there are both positive and negative values, all negative sequence now return the correct result. In my opinion.
48 s1 = [3, -4, 8, -5, 0, 2, 6, -7, 6]
49 s2 = [-1, 3, 5, -2, 3, 0, -2, 9, -2, 3, -1]
50 s3 = [2, -2, 3, 2, 32, -5, -2, 8, -3, 11, 0, -11, -3, 5, -1]
51 s4 = [3, -4]
52 s5 = [-4, 3, 56, -15, 34, 0, -14, 4]
53 s6 = [-4, -3, -1, -5, -2]
54 ss = [s1, s2, s3, s4, s5, s6]
55 line()
56 
57 for s in ss:
58     show(s)

结果是这样。原序列；cur的更新过程；（最后结果，子序列起始下标，子序列结束下标）都很清楚

 1 *************************************
 2 [3, -4, 8, -5, 0, 2, 6, -7, 6]
 3 [3, -1, 8, 3, 3, 5, 11, 4, 10]
 4 (11, 2, 6)
 5 *************************************
 6 [-1, 3, 5, -2, 3, 0, -2, 9, -2, 3, -1]
 7 [-1, 3, 8, 6, 9, 9, 7, 16, 14, 17, 16]
 8 (17, 1, 9)
 9 *************************************
10 [2, -2, 3, 2, 32, -5, -2, 8, -3, 11, 0, -11, -3, 5, -1]
11 [2, 0, 3, 5, 37, 32, 30, 38, 35, 46, 46, 35, 32, 37, 36]
12 (46, 2, 9)
13 *************************************
14 [3, -4]
15 [3, -1]
16 (3, 0, 0)
17 *************************************
18 [-4, 3, 56, -15, 34, 0, -14, 4]
19 [-4, 3, 59, 44, 78, 78, 64, 68]
20 (78, 1, 4)
21 *************************************
22 [-4, -3, -1, -5, -2]
23 [-4, -3, -1, -5, -2]
24 (-1, 2, 2)
25 *************************************