Design Based DOT NET

        求連續子序列最大和的問題是一個很有趣的問題，我們在學習程序語言時經常會做一些這樣的練習。這個之所以有趣，是因為有很多算法可以解決它，而這些算法的性能又相差很。下面給出用boo語言實現的三種解決方法：

1、最簡單的方法就是直接窮盡查找，即遍歷所有可能的子序列，對每一個可能的子序列，計算出它們的和，最後返回最大的和。

01 import System  
02 def maxSubsequenceSum1(*args as (int)):  
03     maxSum = 0  
04     for i in range(args.Length):  
05         for j in range(i, args.Length):  
06             thisSum = 0  
07             for k in range(i, j):  
08                 thisSum += args[k]  
09                 if thisSum > maxSum:  
10                     maxSum = thisSum  
11                     seqStart = i  
12                     seqEnd = j  
13       
14     return maxSum

這個方法的優點就是極其簡單，然而通常這種算法效率卻不是很好。

2、如果我們從上面的方法中刪除一個循環，就可以降低這個算法的運行時間。通過觀察可以看到上面的算法有很多不必要的計算，我們可以將內層的for循環去掉，以提高效率。 

01 import System  
02 def maxSubsequenceSum2(*args as (int)):
03     maxSum = 0  
04     for i in range(args.Length):  
05         thisSum = 0  
06         for j in range(i, args.Length):  
07             thisSum += args[j]  
08             if thisSum > maxSum:  
09                 maxSum = thisSum  
10                 seqStart = i  
11                 seqEnd = j
12     
13     return maxSum

3、可以看出第二個算法的效率與第一個相比，已經提高很多了，但第二個算法還是窮盡查找，也就是說，我們還是測試了所有可能的子序列。我們可以從中排除很多不可能的子序列。下面我給出第三個算法的實現代碼，對於這個算法的正確性，可以通過數學推理去證明。

01 import System
02 def maxSubsequenceSum3(*args as (int)):  
03     maxSum = 0  
04     thisSum = 0  
05     for j in range(args.Length):  
06         i = 0  
07         thisSum += args[j]  
08         if thisSum > maxSum:  
09             maxSum = thisSum  
10             seqStart = i  
11             seqEnd = j  
12         elif thisSum < 0:  
13             i = j + 1  
14             thisSum = 0  
15
16     return maxSum

為了你的幸福，我一直在努力！