最长递增和递减序列序列的暴力求解---C语言版

最长递增子序列的求解，也是经常出现在找工作笔试面试中的一类问题。这里是我自己用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");
}
}


}