最长递增子序列的求解,也是经常出现在找工作笔试面试中的一类问题。这里是我自己用C语言写的一个暴力解法。。。哈哈,暴力的才是最简单的,万一以后在线笔试的时候遇到这类问题,直接拿过来用就好了。这里我定义了一个结构体,不仅记录了最长的子序列的大小,还记录了依次是哪几个数字,非常实用方便。
点击(此处)折叠或打开
-
#pragma warning(disable:4996)
-
#include<stdio.h>
-
#include<string.h>
-
#define MAX_LEN 20
-
typedef struct {
-
int length;
-
int a[MAX_LEN];
-
}node;
-
//将一个整形数组中的值拷贝到另一个整形数组中
-
IntStringcpy(node *dst, node src) {
-
for (int i = 0; i < src.length; i++) {
-
(*dst).a[i] = src.a[i];
-
(*dst).length = src.length;
-
}
-
}
-
Intcpy(node* dst, int num) {
-
int length = (*dst).length;
-
(*dst).a[length] = num;
-
(*dst).length++;
-
}
-
-
LIS(int num[], node dp[],int length) {
-
int i = 1, j = 0; dp[0].a[0] = num[0];
-
for (; i < length; i++) {
-
for (j=0; j < i; j++) {
-
if ((num[j] < num[i]) && dp[i].length < dp[j].length+1) {
-
//现将dp[j]中的数组a拷贝到dp[j]的数租dp[i]之中。
-
IntStringcpy(&dp[i],dp[j]);
-
}
-
}
-
//对某个i节点结束之后,也将其放在dp数组中,同时length自增1次
-
Intcpy(&dp[i],num[j]);
-
}
-
}
-
-
int main(void) {
-
int n;
-
scanf("%d", &n);
-
int array[MAX_LEN];
-
for (int i = 0; i < n; i++) {
-
scanf("%d", &array[i]);
-
}
-
node dp[MAX_LEN];
-
for (int i = 0; i < n; i++)
-
dp[i].length = 1;
-
-
LIS(array, dp, n);
-
int max = dp[0].length;
-
for (int i = 1; i < n; i++) {
-
if (max < dp[i].length) {
-
max=dp[i].length;
-
}
-
}
-
for (int i = 0; i < n; i++) {
-
if (dp[i].length == max) {
-
for (int j = 0; j < max; j++) {
-
printf("%d ", dp[i].a[j]);
-
}
-
printf("\n");
-
}
-
}
-
- }
今天又更新了下,写了个最长递减子序列的,思路是一样的,值得注意的是角标,很容易出错弄得不好的话.。。。
点击(此处)折叠或打开
-
#pragma warning(disable:4996)
#include<stdio.h>
#include<string.h>
#define MAX_LEN 20
typedef struct {
int length;
int a[MAX_LEN];
}node;
//将一个整形数组中的值拷贝到另一个整形数组中
void IntStringcpy(node *dst, node src) {
for (int i = 0; i < src.length; i++) {
(*dst).a[i] = src.a[i];
(*dst).length = src.length;
}
}
void Intcpy(node* dst, int num) {
int length = (*dst).length;
(*dst).a[length] = num;
(*dst).length++;
}
void LDS(int num[], node dp[], int n) {
int i = n-2, j;
dp[n - 1].a[0] = num[n - 1]; dp[n - 1].length = 1;
for (; i >=0; i--) {
for (j = n-1; j > i; j--) {
if ((num[j] < num[i]) && dp[i].length < dp[j].length + 1) {
//现将dp[j]中的数组a拷贝到dp[j]的数租dp[i]之中。
IntStringcpy(&dp[i], dp[j]);
}
}
//对某个i节点结束之后,也将其放在dp数组中,同时length自增1次
Intcpy(&dp[i], num[j]);
}
}
int main(void) {
int n;
scanf("%d", &n);
int array[MAX_LEN];
for (int i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
node dp[MAX_LEN];
for (int i = 0; i < n; i++)
dp[i].length = 0;
LDS(array, dp, n);
int max = dp[n-1].length;
for (int i = n-2; i >=0; i--) {
if (max < dp[i].length) {
max = dp[i].length;
}
}
for (int i =n-1; i >=0; i--) {
if (dp[i].length == max) {
for (int j = max-1;j>=0; j--) {
printf("%d ", dp[i].a[j]);
}
printf("\n");
}
}
}