设计一个O(n2)时间的算法, 找出由n个数组成的序列的最长单调递增子序列。

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include 

int main()
{
	//时间复杂度为O(n2)：两层循环，外层最大循环次数n，内层最大循环次数n，最大共计n2，也称平方阶
	//设计一个O(n2)时间的算法, 找出由n个数组成的序列的最长单调递增子序列。
	
	//最长递增子序列（Longest Increasing Subsequence，LIS) 指的是找到一个特定的最长的子序列，并且子序列中的所有元素单调递增。
	//例如，{ 3，5，7，1，2，8 } 的 LIS 是{ 3，5，7，8 }，长度为 4
	
	//创建数组并初始化
	int array[] = { 11, 1, 2, 3, 5, 3, 9};
	
	int SIZE = sizeof(array) / sizeof(array[1]); 

	int i, j;
	int* pa = array;
	int temp = 0, count = 1; //count计算子序列的元素个数
	//冒牌排序现将数组排列好
	int* parray = (int*)malloc(SIZE * sizeof(int)); //创建一个动态内存区域，用来存放子序列元素的地址,子序列元素个数小于等于数组元素个数，使用SIZE个int字节，足矣
	if (parray == NULL)
	{
		perror("parray"); //避免空指针
		return 0;
	}

	for (i = 0; i < SIZE - 1; i++)
	{
		for(j = 0; j < SIZE -1 - i; j++)
		{
			if (array[j] > array[j + 1])
			{
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}	
	}
	//遍历一下数组，检查
	for (i = 0; i < SIZE; i++)
	{
		printf("%d ", array[i]);
	}
	printf("n");
	

	//将元素添加到动态内存区
	*parray = array[0]; //动态内存区的第一个元素是数组的首元素
	for (i = 0, j = 0; i < SIZE - 1; i++)
	{
		if (*(pa + i + 1) > array[i])
		{
			temp = count;
			count++;
			//问题出现在这里：
			//*(parray + i + 1) = array[i + 1]; 动态内存区的空间和静态内存区的空间一起跳了，这这个程序中，动态内存区和静态内存区是不同步的
			if (count > temp)
			{
				*(parray + j + 1) = array[i + 1];
				j++;
			}
		}
	}

	//输出子序列及其个数，
	printf("%dn", count);
	for (i = 0; i < count; i++)
	{
		printf("%d ", *(parray+i));
	}

	free(parray);
	parray = NULL;
	
	return 0;
}
 No newline at end of file

运行结果：