学步园

 2 查看了一下别人的优化算法 联机算法 时间复杂度仅为O(n)，如下：
 sum
= a[1], temp = a[1];

 for(int i = 2; i <= n; i++){

   
    if(sum >
0)

   
   
   
 temp += a[i];

   
    else

   
   
   
 temp = a[i];

   
    if(temp >
sum)

   
   
   
 sum = temp;

 
 } 

     
时间复杂度： T(n) = O(n)。
联机算法：
 
在任意时刻，算法都能对它已经读入的数据给出子序列问题的正确答案。具有这种特性的算法叫做联机算法（on-line
algorithm）。仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法。

 
我对这个算法顶礼膜拜不已，仅需要一个整形变量的空间辅助，并且仅仅一个循环便貌似轻松搞定问题。
 
然后是考虑边界以及输入的各种可能性，对于边界，该算法仅有和式运算，不是钻牛角尖的话一般不会有溢出，但如果真要考虑这点，则可以将sum以及temp设置为long型。对于输入，假设给出的数组中元素全部为负数，上述算法也能找出单个最大的那个元素并输出，也没问题。

  问题的深入：假设我想获取这个连续最大的字序列，算法又该如何？接下来有更新。