首页实现一个算法查找一个无序整数数组最长的上升子序列c语言

实现一个算法查找一个无序整数数组最长的上升子序列c语言

时间: 2025-06-22 13:38:59 浏览: 8

### C语言实现查找无序整数数组中最长上升子序列为了在C语言中实现查找无序整数数组中的最长上升子序列，可以采用动态规划的方法。这种方法的时间复杂度为O(n^2)，其中n是数组的大小。下面是一个完整的C语言程序示例： ```c #include <stdio.h> #include <stdlib.h> // 函数用于获取两个整数的最大值 int max(int a, int b) { return (a > b)? a : b; } // 动态规划函数计算最长上升子序列的长度 void longestIncreasingSubsequence(int arr[], int n) { // 创建dp数组存储到当前位置为止的最长上升子序列长度 int *dp = (int *)malloc(sizeof(int)*n); // 初始化dp数组，默认每个位置至少有1个元素构成的上升子序列 for (int i = 0; i < n; ++i) dp[i] = 1; // 构建dp表 for (int i = 1; i < n; ++i){ for (int j = 0; j < i; ++j){ if (arr[i] > arr[j] && dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } } // 找出最大值即为所求的结果 int maxLength = 0; for (int i = 0; i < n; ++i) if (maxLength < dp[i]) maxLength = dp[i]; printf("The length of the Longest Increasing Subsequence is %d\n", maxLength); free(dp); // 释放分配的空间 } int main() { int arr[] = {10, 9, 2, 5, 3, 7, 101, 18}; int n = sizeof(arr)/sizeof(arr[0]); longestIncreasingSubsequence(arr, n); return 0; } ``` 此代码实现了基于动态规划原理寻找最长上升子序列的功能[^3]。通过构建`dp`数组记录每一个可能成为结尾的位置对应的最长上升子序列长度，并最终返回这些数值中的最大者作为结果。

阅读全文