首页 > 其他 > 详细

Geeks 面试题: Longest Bitonic Subsequence

时间:2014-02-02 18:42:58      阅读:386      评论:0      收藏:0      [点我收藏+]

Longest Bitonic Subsequence

Given an array arr[0 ... n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing. Write a function that takes an array as argument and returns the length of the longest bitonic subsequence.
A sequence, sorted in increasing order is considered Bitonic with the decreasing part as empty. Similarly, decreasing order sequence is considered Bitonic with the increasing part as empty.


Examples:


Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)


Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)


Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)


算法是根据我的另一篇博客改变而来的:

http://blog.csdn.net/kenden23/article/details/18350315

这里的技巧是两边扫描,然后合起来,时间效率也是O(n*n),和求最大递增子段和一样。

两边扫描是个经典技巧,一定要记得,掌握。

Geeks上原文和我的算法效率一样,处理起来有区别。

int lbsMyDP( int arr[], int n )
{
	vector<int> ta(n, 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (arr[j] > arr[i]) ta[j] = ta[i]+1;
		}
		if (i > 1) ta[i] = max(ta[i], ta[i-1]);
	}
	vector<int> ta2(n, 1);
	for (int i = n - 1; i >= 0 ; i--)
	{
		for (int j = i - 1; j >= 0 ; j--)
		{
			if (arr[j] > arr[i]) ta2[j] = ta2[i]+1;
		}
		if (i < n - 1) ta2[i] = max(ta2[i], ta2[i+1]);
	}
	int len = 0;
	for (int i = 1; i < n; i++)
	{
		len = max(ta[i-1]+ta2[i], len);
	}
	return len;
}



Geeks 面试题: Longest Bitonic Subsequence

原文:http://blog.csdn.net/kenden23/article/details/18351477

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!