求最长上升序列的代码实现
时间: 2023-03-10 15:08:54 浏览: 58
我可以给出一份最长上升序列的代码实现: int longestIncreasingSubsequence(int arr[], int n)
{
int lis[n];
/* Initialize LIS values for all indexes */
for (int i = 0; i < n; i++ )
lis[i] = 1;
/* Compute optimized LIS values in bottom up manner */
for (int i = 1; i < n; i++ )
for (int j = 0; j < i; j++ )
if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
lis[i] = lis[j] + 1;
// Return maximum value in lis[]
int max = 0;
for (int i = 0; i < n; i++ )
if ( max < lis[i] )
max = lis[i];
return max;
}
相关问题
求最长上升序列的动态规划代码实现
动态规划求解最长上升序列的代码实现应该是这样的:int max_length = 0;for (int i = 0; i < n; i++) {
int length = 1;
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i] && length < (dp[j] + 1)) {
length = dp[j] + 1;
}
}
dp[i] = length;
max_length = max(length, max_length);
}return max_length;
最长上升子序列求方案C++代码
以下是最长上升子序列求方案的C代码:
```
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n, i, j, max = 0, max_index = 0;
scanf("%d", &n);
int *a = (int*)malloc(n * sizeof(int));
int *dp = (int*)malloc(n * sizeof(int));
int *pre = (int*)malloc(n * sizeof(int));
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
dp[i] = 1;
pre[i] = -1;
for(j = 0; j < i; j++)
{
if(a[j] < a[i] && dp[j] + 1 > dp[i])
{
dp[i] = dp[j] + 1;
pre[i] = j;
}
}
if(dp[i] > max)
{
max = dp[i];
max_index = i;
}
}
printf("%d\n", max);
int *ans = (int*)malloc(max * sizeof(int));
for(i = max - 1; i >= 0; i--)
{
ans[i] = a[max_index];
max_index = pre[max_index];
}
for(i = 0; i < max; i++)
{
printf("%d ", ans[i]);
}
printf("\n");
free(a);
free(dp);
free(pre);
free(ans);
return 0;
}
```
希望能对您有所帮助!