c语言最长递增序列

求解一个数组的最长递增子序列（Longest Increasing Subsequence, LIS）是一个经典的动态规划问题。以下是C语言实现最长递增子序列的代码：

#include <stdio.h>

int lis(int arr[], int n)
{
    int dp[n], 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\n", lis(arr, n));
    return 0;
}

输出结果为：

Length of LIS is 5

这个算法的时间复杂度是 $O(n^2)$。

相关问题

c语言最长递增子序列

求解 C 语言的最长递增子序列可以使用动态规划算法，具体步骤如下：

1. 定义一个一维数组 dp，长度为原数组长度，dp[i] 表示以第 i 个元素结尾的最长递增子序列长度。

2. 初始化 dp 数组，将每个元素的最长递增子序列长度初始化为 1。

3. 遍历原数组，对于第 i 个元素，从 0 到 i-1 依次枚举前面的元素 j，若 nums[i] 大于 nums[j]，则更新 dp[i]，取 dp[j] + 1 和 dp[i] 中的较大值。

4. 遍历 dp 数组，取最大值即为最长递增子序列长度。

以下是 C 语言代码实现：

#include <stdio.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int LIS(int nums[], int n) {
    int dp[n];
    int res = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = max(res, dp[i]);
    }
    return res;
}

int main() {
    int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};
    int n = sizeof(nums) / sizeof(nums[0]);
    printf("最长递增子序列长度为：%d\n", LIS(nums, n)); // 输出：最长递增子序列长度为：4
    return 0;
}

pta C语言最长连续递增子序列

在C语言中，求解最长连续递增子序列（Longest Increasing Subsequence, LIS）通常是一个经典的问题，可以使用动态规划方法来解决。这个问题的目标是找出一个给定数组中最长的子序列，其中每个元素都大于前一个元素。

这里有一个常见的Kadane's算法的例子：

#include <stdio.h>
#include <stdlib.h>

int longest_increasing_subsequence(int arr[], int n) {
    if (n == 0)
        return 0;

    // 初始化一个长度为n的一维数组dp，所有元素都是1（因为每个元素本身都是其自身的子序列）
    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++) {
            // 如果当前元素大于前一个元素，更新dp[i]为dp[j]+1，如果新值更大，则更新
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    // 最后，返回dp数组中的最大值作为结果
    int result = *max_element(dp, dp + n);
    return result;
}

// 使用max函数需要包含头文件
// #include <algorithm>

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

这个程序会计算并输出给定整数数组`arr`中最长的递增子序列的长度。如果你有其他问题或需要进一步的解释，请告诉我。