求最长递增子序列c语言

以下是求最长递增子序列的 C 语言实现代码：

#include <stdio.h>

int lis(int arr[], int n) {
    int dp[n], max_len = 1;

    // 初始化 dp 数组
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    // 计算最长递增子序列的长度
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
        }
    }

    return max_len;
}

int main() {
    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("最长递增子序列的长度为：%d\n", lis(arr, n));
    return 0;
}

该算法的时间复杂度为 O(n^2)，其中 n 是数组的长度。

相关问题

最长递增子序列c语言

以下是 C 语言实现最长递增子序列的代码：

#include <stdio.h>

int lis(int arr[], int n)
{
    int dp[n];
    int max = 0;
 
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > max) {
            max = dp[i];
        }
    }
 
    return max;
}
 
int main()
{
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of LIS is %d", lis(arr, n));
    return 0;
}

该算法的时间复杂度为 O(n^2)，其中 n 是数组的长度。

输出最长递增子序列c语言

在C语言中，求解最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题。动态规划方法通常用于解决这类具有重叠子问题和最优子结构的问题。这里是一个简单的算法概述：

1. 创建一个数组dp，长度与输入数组相同，用于存储每个位置的最大递增子序列长度。

2. 初始化数组dp的所有元素为1，因为每个数字本身都是一个长度为1的递增子序列。

3. 遍历输入数组nums：
a. 对于每个元素nums[i]，从0到i-1遍历所有之前处理过的元素nums[j]（j < i），如果nums[j] < nums[i]并且dp[j]+1 > dp[i]，更新dp[i]为dp[j]+1。

4. 在遍历结束后，dp数组的最后一个元素就是整个序列中最长的递增子序列的长度。

5. 要找出具体的递增子序列，可以在dp数组中记录下每个位置对应的最大前驱，通过回溯找到这个序列。

下面是简化版的C语言代码示例：

#include <stdio.h>

int lis(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    // 回溯找出最长递增子序列
    int max_len = *max_element(dp, dp+n);
    int* lcs = malloc(sizeof(int) * max_len);
    int index = n - 1, length = max_len;
    while (length > 0) {
        for (int i = n - 1; i >= 0; i--) {
            if (dp[i] == length && arr[i] > lcs[length - 1]) {
                lcs[length - 1] = arr[i];
                index = i;
                break;
            }
        }
        length--;
    }
    
    printf("最长递增子序列为: ");
    for (int i = max_len - 1; i >= 0; i--) {
        printf("%d ", lcs[i]);
    }
    free(lcs);
    return max_len;
}

int main() {
    int arr[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Length of longest increasing subsequence is %d\n", lis(arr, n));
    return 0;
}