问题描述：

给定一整数序列A1， A2，... An （可能有负数），求A1_{An的一个子序列Ai}Aj，使得Ai到Aj的和最大 。

算法（时间复杂度为O(n)）

解析：
假设arr[i]为负数，则arr[i]不可能为此子序列的起始，同理，若arr[i]到arr[j]的子序列为负，则arr[i]到arr[j]不可能为子序列的起始，则可以从arr[j+1]开始推进，
实现：
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;
}

只对数据进行一次扫描，一旦a[i]被读入并处理，它就不再需要被记忆。因此数组可以被按顺序读入，在主存中不必存储数组的任何部分。具有这种特性的算法叫联机算法(on-line algorithm)，仅需要常量空间并以线性时间运行的联机算法几乎是完美算法！

对于此问题还有别的方法，但是这个方法的时间复杂度最好，这个问题化繁为简的根本我觉得就是一种宏观的思想，在宏观上观察问题的规律或特点，会更容易发现优秀的算法。