最大子序列和问题的求解（时间复杂度为O(N)）

//时间复杂度为O(N)的最大子序列和问题的求解
public static int maxSubSum4(int [] a){
    int maxSum = 0,thisSum = 0;
    for(int j = 0;j<a.length;j++){
         thisSum += a[j];
         if(maxSum < thisSum)
             maxSum = thisSum;
         else if(thisSum<0)
             thisSum = 0;
    }
    return maxSum;
}

由于负数（负子序列）不可能作为最大子序列的起始点，因此，可以通过上述方法寻找出最大子序列。