posts - 71, comments - 39, trackbacks - 0

计算最长递增子序列的长度

template < class T >

int GetLISLen(T * arr, int n)

{

if (n < 1 )

return 0 ;

int iCurrMaxLen = 0 ;

int left, right, mid;

int * last = new int [n]();

last[ 0 ] = arr[ 0 ];

for ( int i = 1 ; i < n; i ++ )

{

if (arr[i] >= last[iCurrMaxLen])

last[ ++ iCurrMaxLen] = arr[i];

else if (arr[i] < last[ 0 ])

last[ 0 ] = arr[i];

else

{

left = 0 ;

right = iCurrMaxLen;

while (left != right - 1 )

{

mid = (left + right) / 2 ;

(last[mid] <= arr[i]) ? (left = mid) : (right = mid);

}

last[right] = arr[i];

} // if

} // for

for ( int i = 0 ; i < iCurrMaxLen + 1 ; i ++ )

{

printf( " %d " , last[i]);

if (i != iCurrMaxLen)

printf( " \x20 " );

else

printf( " \n " );

}

if (last)

{

delete [] last;

last = 0 ;

}

return iCurrMaxLen + 1 ;

}

posted on 2006-11-22 17:45 Charles 阅读(370) 评论(0) 编辑收藏引用所属分类: 面试小算法

IT新闻：
· Windows Phone 7模拟器及其视频
· 传51.com战略投资彩虹浏览器
· 数据显示微软浏览器开始丧失欧洲市场份额
· NVIDIA发布CUDA 3.0 新特性抢先看
· 再谈 Chrome 浏览器的安全功能

专题：Android iPad jQuery Chrome OS

博客园首页 IT新闻知识库学英语 C++程序员招聘

标题

姓名

主页


验证码	*

内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)

Remember Me?

登录使用高级评论新用户注册返回页首恢复上次提交

[使用Ctrl+Enter键可以直接提交]

每天10分钟，轻松学英语

博客园首页随笔：
· [译].Google Chrome extensions（实验室）.界面.选项
· Visual Studio 2010 XAML Editor IntelliSense Extension
· 取之于民用之于民，分享一个云计算PPT（普及版）
· Lighttpd1.4.20源码分析之fdevent系统（4） -----连接socket的处理与超时处理
· 带实例数据的和动手实验室的Visual Studio 2010 RC 虚拟机下载

知识库：
· 时间管理——专注与放下
· 再谈Share-Nothing体系结构
· 自学之路——为今后的30年做准备
· 技术、业务、市场
· 五个广泛流传的对大龄程序员的误解

网站导航:

博客园 IT新闻博客园个人主页 BlogJava 博客生活 IT博客网 PHP博客博客园社区管理

2006年11月

日

一

二

三

四

五

六

决定开始写工作日记，记录一下自己的轨迹...

常用链接

留言簿(3)

随笔分类(70)

随笔档案(71)

相册

charles推荐访问

搜索

积分与排名

积分 - 23630
排名 - 185

常用链接

留言簿(3)

随笔分类(70)

随笔档案(71)

相册

charles推荐访问

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜