在線上算法是在任意時刻算法對要操作的數據唯讀入（掃描）一次，一旦被讀入並處理，它就不需要在被記憶了。而在此處理過程中算法能對它已經讀入的數據立即給出相應子序列問題的正確答案。
基本介紹
- 中文名：在線上算法
- 方法一：遞歸調用（易懂）
- 示例：求 一個 序列中的最大子序列
- 優點：占用空間少，所用時間少
完美的算法,優點,缺點,示例,方法一：遞歸調用（易懂）,方法二：（在線上算法）,
完美的算法
該算法僅需要常量空間並以線性時間運行，因此在線上算法幾乎是完美的算法。
優點
占用空間少，所用時間少
缺點
不宜設計，正確性不易觀察，同時附加保留信息較少
示例
求 一個 序列中的最大子序列
方法一：遞歸調用（易懂）
int max( int x, int y, int z ){ int m = x > y ? x : y; int n = m > z ? m : z; return(n);}int MaxSub( const vector<int> & a, int left, int right ){ if ( left == right ) /* 基準情形 */ { if ( a[left] > 0 ) return(a[left]); else return(0); } int mid = (left + right) / 2; int maxLeftSum = MaxSub( a, left, mid ); /* 左右子序列遞歸 */ int maxRightSum = MaxSub( a, mid + 1, right ); int maxLeftBorder = 0, tmpLeft = 0; for ( int i = mid; i >= left; i-- ) { tmpLeft += a[i]; if ( tmpLeft > maxLeftBorder ) { maxLeftBorder = tmpLeft; } } int maxRightBorder = 0, tmpRight = 0; for ( int i = mid + 1; i <= right; i++ ) { tmpRight += a[i]; if ( tmpRight > maxRightBorder ) { maxRightBorder = tmpRight; } } return(max( maxLeftSum, maxRightSum, maxRightBorder + maxLeftBorder ) );}方法二：（在線上算法）
int Max_sub( const vector<int> & a, int left, int right ) /* left right 分別指下標 */{ int tmp = 0, maxSum = 0; for ( int i = left; i <= right; i++ ) { tmp += a[i]; if ( tmp > maxSum ) maxSum = tmp; else if ( tmp < 0 ) tmp = 0; } return(maxSum);}從上可看出，在線上算法不僅在 代碼量上 遠遠 少於方法一，同時 在占用空間（遞歸占用大量的棧）和運行時間上都遠遠優於方法一。
