【C语言】最长子序列问题求解

布满荆棘的人生 2022-08-05 01:17 136阅读 0赞

二维数组，求取最长递增子序列，要求前一个点的横纵坐标都必须小于后面的点，且该点对应的值应不大于后续的值。

以每个点为起点的最长递增子序列

MAZE\[SIZE\]\[SIZE\] – 对应的数组

value\[SIZE\]\[SIZE\] - 记录每一个点为起点的最长子序列的长度

最后一行 最后一列 都填写 1

求value(i,j) 的值。

常规解法：遍历 i+1,j+1 到 size-1,size-1 里面所有的 value值，满足，MAZE\[i\]\[j\] < MAZE\[k\]\[m\] 时，求取最大的 value值。这样做需要四层 For 循环，会造成超时。

超时源代码：

#include <stdio.h>
 #include <string.h>
 
 #define MAX_SIZE 257
 
 int Answer;
 int size;
 int MAZE[MAX_SIZE][MAX_SIZE];
 int temp[MAX_SIZE][MAX_SIZE];
 
 void count (int i, int j);
 
 int main(void)
 {
 	int T, test_case;
 	freopen("input.txt", "r", stdin);
 
 	setbuf(stdout, NULL);
 
 	scanf("%d", &T);
 	for(test_case = 0; test_case < T; test_case++)
 	{
 		Answer = 0;
 
 		int i = 0;
 		int j = 0;
 		size = 0;
 
 		memset(MAZE,0,sizeof(MAZE));
 		memset(temp,0,sizeof(temp));
 
 		scanf("%d",&size);
 
 		for (i = 0; i < size; i++)
 		{
 			for (j = 0; j < size; j++)
 			{
 				scanf("%d",&MAZE[i][j]);
 
 				if (i == size-1 || j == size-1)
 				{
 					temp[i][j] = 1;
 				}
 			}
 		}
 
 		for (i = size-2; i >= 0; i--)
 		{
 			for (j = size-2; j >= 0; j--)
 			{
 				if (temp[i][j] != 0)
 					continue;
 
 				count(i,j);
 				Answer = Answer > temp[i][j] ? Answer : temp[i][j];
 			}
 		}
 
 		printf("Case #%d\n", test_case+1);
 		printf("%d\n", Answer);
 	}
 
 	return 0;
 }
 
 void count (int i, int j)
 {
 	int k,m;
 
 	for (k = i+1; k < size-temp[i][j]; k++)
 	{
 		for (m = j+1; m < size-temp[i][j]; m++)
 		{
 			if (MAZE[k][m] >= MAZE[i][j])
 			{
 				if (temp[k][m]+1 > temp[i][j] && temp[k][m]+1 > temp[i][j])
 				{
 					temp[i][j] = temp[k][m]+1;
 				}
 			}
 		}
 	}
 }

于是，我们需要储存中间的值，以减少遍历的次数，达到优化算法的目的。

那么问题来了，也是很不好想的是，如何保存中间值？？

最后的想法是，每一个value值只存储对应的最大的MAZE值，因为MAZE越大，组成最长子序列的长度的概率会越大。

**于是想到，新建一个一维数组，vmax\[SIZE\]。vmax\[i\] 对应着 value = i 时 对应的最大MAZE值。**

对于value(i,j),需要组成 i+1,j+1 到 size-1,size-1 对应的 vmax\[SIZE\] 数组。

Vmax\[1\] = 4;

Vmax\[1\] = 7 > 4 ? 7 : 4 = 7

Vmax\[1\] = 7 > 6 ? 7 : 6 = 7

到达第二行，清空 Vmax数组，可以看出关系，每一行对应的只是应该把之前没有访问过得点，进行比较更新 Vmax数组对应的值。每次只是让新的一列进入更新。

以下是程序：

for (i = size-2; i >= 0; i--)
 		{
 			flag = 0;
 			memset(vmax,0,sizeof(vmax));
 
 			for (j = size-2; j >= 0; j--)
 			{
 				for (k = i+1; k < size; k++)
 				{
 					vmax[temp[k][j+1]] =
 							vmax[temp[k][j+1]] > MAZE[k][j+1] ? vmax[temp[k][j+1]] : MAZE[k][j+1];
 					flag = temp[k][j+1] > flag ? temp[k][j+1] : flag;
 				}
 
 				int find = 0;
 
 				for (m = flag; m > 0; m--)
 				{
 					if (MAZE[i][j] <= vmax[m])
 					{
 						find = 1;
 						temp[i][j] = m+1;
 						break;
 					}
 				}
 
 				if (!find)
 				{
 					temp[i][j] = 1;
 				}
 			}
 		}
 ///

全部的源代码如下:

//

include <stdio.h>
 #include <string.h>
 
 #define MAX_SIZE 257
 
 int Answer;
 int size;
 int MAZE[MAX_SIZE][MAX_SIZE];
 // 以 i j 为起点的最长子序列
 int temp[MAX_SIZE][MAX_SIZE];
 int vmax[MAX_SIZE];
 
 int main(void)
 {
 	int T, test_case;
 	freopen("input.txt", "r", stdin);
 
 	setbuf(stdout, NULL);
 
 	scanf("%d", &T);
 	for(test_case = 0; test_case < T; test_case++)
 	{
 		int i = 0;
 		int j = 0;
 		int k = 0;
 		int m = 0;
 		int flag = 0;
 
 		size = 0;
 		Answer = 0;
 
 		memset(MAZE,0,sizeof(MAZE));
 		memset(temp,0,sizeof(temp));
 		memset(vmax,0,sizeof(vmax));
 
 		scanf("%d",&size);
 
 		for (i = 0; i < size; i++)
 		{
 			for (j = 0; j < size; j++)
 			{
 				scanf("%d",&MAZE[i][j]);
 
 				if (i == size-1 || j == size-1)
 				{
 					temp[i][j] = 1;
 				}
 			}
 		}
 
 		for (i = size-2; i >= 0; i--)
 		{
 			flag = 0;
 			memset(vmax,0,sizeof(vmax));
 
 			for (j = size-2; j >= 0; j--)
 			{
 				for (k = i+1; k < size; k++)
 				{
 					vmax[temp[k][j+1]] =
 							vmax[temp[k][j+1]] > MAZE[k][j+1] ? vmax[temp[k][j+1]] : MAZE[k][j+1];
 
 					flag = temp[k][j+1] > flag ? temp[k][j+1] : flag;
 				}
 
 				int find = 0;
 
 				for (m = flag; m > 0; m--)
 				{
 					if (MAZE[i][j] <= vmax[m])
 					{
 						find = 1;
 						temp[i][j] = m+1;
 
 						if (m == flag && temp[i][j] > Answer)
 						{
 							Answer = temp[i][j];
 						}
 
 						break;
 					}
 				}
 
 				if (!find)
 				{
 					temp[i][j] = 1;
 				}
 			}
 		}
 
 		printf("Case #%d\n", test_case+1);
 		printf("%d\n", Answer);
 	}
 
 	return 0;
 }