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 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;
}