Geeksforgeeks面试题 - Longest Increasing Subsequence

Longest Increasing Subsequence

The longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, length of LIS for { 10, 22, 9, 33, 21, 50, 41, 60, 80 } is 6 and LIS is {10, 22, 33, 50, 60, 80}.


注意题目要求：
1 所选的数值不必连续，可以间隔， 但是顺序不能乱
2 其中的间隔不用计算，只计算所选数的长度就可以

思路：

1 从最小两个开始计算。

2 计算i个数值的时候，只需要比较A[i]数值和i前所有数值，只要A[i]比任何一个数值A[j]大，那么动态规划表v[i]就在选取v[j] +1 和v[i]最大的值填上

v[j]+1表示在j个数值之前的最长递增子序列数是v[j]，+1表示加上第i个值A[i]，那么递增子序列就增加了1.

动态规划法很好解决：

int longestIncreaseSubsequence(int A[], int n)
{
	vector<int> v(n, 1);
	int maxL = 1;

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (A[i] > A[j]) v[i] = max(v[i], v[j]+1);
			maxL = max(maxL, v[i]);
		}
	}
	return maxL;
}

int main()
{
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 10 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of LIS is %d\n",  longestIncreaseSubsequence( arr, n ));
    system("pause");
    return 0;
}

测试例子的答案为4