什么是联机算法

如果在任何时刻，算法都能对它已经读入的数据给出子序列问题的正确答案，具有这种特性的算法叫做联机算法。仅需要常量空间并以线形时间运行的联机算法几乎是完美的算法。

一个经典的问题：求最大子序列和的算法就是这样一个完美的算法，给定一个数组（不妨设为整形），求出一个子序列，使得子序列中的元素之和为最大。例如 {4，3，-8，2，6，-2，1}，则 {2，6} 子序列即为所求。

这个问题有很多种算法可以解决，但是最好的是一个线形时间常量空间的联机算法，算法如下：

java 代码

int maxSubSum (int[] a, int size)
{
     int maxSum = 0, thisSum = 0;
     int start = 0, end = 0;

     for ( int j = 1; j <= size; j++ )
     {
           thisSum += a[j-1];

          if (thisSum > maxSum)
          {
               maxSum = thisSum;
               end = j;
          }
          else if (thisSum < 0)
          {
              thisSum = 0;
              maxSum = 0;
              start = j + 1;
          }
     }

      System.out.println(“最大子序列从第” + start + “个元素到第” + end + “个元素”);
      System.out.println("最大子序列和为“ + maxSum);

      return maxSum;
}

可以看出这个算法是线形时间O(N)的，且只对数据进行一次扫描，一旦a[j]被读入并被处理，它就不需要再被记忆。因此如果数组在磁盘或磁带上，它就可以被顺序读入，在主存中不必存储数组的任何部分。所以这个算法是一个几乎完美的联机算法。

分享到：

ADO.net 中数据库连接方式 | 算法分析基础符号

• 2007-06-05 15:15
• 浏览 3474
• 评论(5)
• 查看更多

评论

5 楼 落日枫 2008-03-17  

当被执行数组为 {4，5，-10，2，6，-2，1} 得到的结果是错误的没有得到正确答案，
我想maxsum=0这句代码的原因，丢失了原来的最大值
下面是我的程序，能得到正确答案了，没充分测试过，请大家指出下错误：

#include "stdio.h"
#define N 13
//联机算法
void MaxSunSum(int a[],int n,int result[])
{
int thisSum=0;
int MaxSum=0;
int j,start=1,end=1;
int starttemp=1;
for(j=0;j <N;j++)
{
thisSum+=a[j];
if(thisSum> MaxSum)
{
end=j+1;
MaxSum=thisSum;
start=starttemp;
}
else if(thisSum <0)
{
thisSum=0;
starttemp=j+2;
}
}
result[0]=MaxSum;
result[1]=start;
result[2]=end;//结果数组
}

4 楼 pake007 2007-06-10  

谢谢geng，一时疏忽，在else情况中少加了一句maxSum=0，现在已经改好了

3 楼 geng2483759 2007-06-08  

程序明显不对啊,start的赋值不正确,用这个 {4，5，-10，2，6，-2，1}

结果是start=3,end=1

2 楼 pake007 2007-06-06  

是{2，6}没错的，这里的子序列元素是连续的

1 楼 ouspec 2007-06-05  

求出一个子序列，使得子序列中的元素之和为最大。例如 {4，3，-8，2，6，-2，1}，则 {2，6} 子序列即为所求。


正确的结果应该是{4，6} 吧？