問題描述：
給定一整數(shù)序列A1欣尼， A2摆马，... An （可能有負數(shù)）拓提，求A1An的一個子序列AiAj读恃，使得Ai到Aj的和最大 。
算法（時間復(fù)雜度為O(n)）
解析：
假設(shè)arr[i]為負數(shù)代态，則arr[i]不可能為此子序列的起始寺惫，同理，若arr[i]到arr[j]的子序列為負蹦疑，則arr[i]到arr[j]不可能為子序列的起始西雀，則可以從arr[j+1]開始推進，
實現(xiàn)：
swift：
func MaxSubsequenceSum(arr:inout [Int])-> Int {
var thisSum=0,maxSum=0;
for j in arr {
thisSum += j;
if thisSum>maxSum{
maxSum = thisSum
}else{
thisSum = 0
}
}
return maxSum
}
OC:
- (int)MaxSubsequenceSum:(NSMutableArray *)arr{
int thisSum=0,maxSum=0;
for (int j=0; j<arr.count; j++) {
thisSum += [arr[j] intValue];
if (thisSum>maxSum) {
maxSum = thisSum;
}else{
thisSum = 0;
}
}
return maxSum;
}
只對數(shù)據(jù)進行一次掃描歉摧，一旦a[i]被讀入并處理艇肴，它就不再需要被記憶。因此數(shù)組可以被按順序讀入叁温，在主存中不必存儲數(shù)組的任何部分豆挽。具有這種特性的算法叫聯(lián)機算法(on-line algorithm)，僅需要常量空間并以線性時間運行的聯(lián)機算法幾乎是完美算法券盅！
對于此問題還有別的方法帮哈，但是這個方法的時間復(fù)雜度最好，這個問題化繁為簡的根本我覺得就是一種宏觀的思想锰镀，在宏觀上觀察問題的規(guī)律或特點娘侍，會更容易發(fā)現(xiàn)優(yōu)秀的算法咖刃。
