最长递增子串（Lis）[C#]
子串定义，如下：摘自《参考资料》[1]
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1, x2,…, xm>，则另一序列Z=<z1, z2,…, zk>是X的子序列是指存在一个严格递增的下标序列 <i1, i2,…, ik>，使得对于所有j=1,2,…,k有
例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相应的递增下标序列为<2,3,5,7>。
------------------------------------------------------------------------
思路来自一位pku/cs的前辈，如下：
http://blog.csdn.net/askmyself/archive/2005/01/17/256793.aspx
我的代码实现如下:
/// <summary>
/// 求一个字符串的最长递增子串
/// “动态规划”
/// </summary>
/// <param name="desti">目标串</param>
/// <returns>最长递增子串</returns>
private string Lis(string desti)
{
int len = desti.Length;
int[] lenMax = new int[len];// 用于存放每个位置的串长
for(int i = 0; i < len; i ++)//初始化每个位置的串长
lenMax[i] = 1;
int[] maxIndex = new int[len];
for(int i = 0; i < len; i ++)
{
int tempMaxIndex = 0;
int tempMaxLen = 0;
//该循环用来寻找desti[i]之前的最大字符及其下标
for(int j = 0; j < i; j ++)
{
if(desti[j] < desti[i] && lenMax[j] > tempMaxLen)
{
tempMaxLen = lenMax[j];
tempMaxIndex = j;
}
}
//位置i的串长
lenMax[i] = tempMaxLen + 1;
maxIndex[i] = tempMaxIndex;
}
string result = string.Empty;
int maxLen = 1;
int maxLenIndex = 0;
//最长递增子串长度
for(int i = 0; i < len; i ++)
{
if(lenMax[i] > maxLen)
{
maxLen = lenMax[i];
maxLenIndex = i;
}
}
//结果串
int l = 0;
Stack stack = new Stack();
for(int i = maxLenIndex; i >= 0 ;)
{
stack.Push(desti[i]);
i = maxIndex[i];
l ++;
if(l == maxLen)
break;
}
for(int i = 0; i < maxLen; i ++)
result +=((char)stack.Pop()).ToString();
return result;
}
参考资料：
[1]http://algorithm.diy.myrice.com/problems/index.html?classic/index.htm
[2]《Introduction to Algorithems》作者：Thomas H. Cormen ，Charles E. Leiserson ，Ronald L. Rivest ，Clifford St
ein
