如何使用C语言编写并详细注释的动态规划算法来解决最长单调递增子序列的问题？给出一个具有N个元素的数组作为输入，并解释算法如何处理不连续但保持顺序的子序列，最终输出该子序列的最大长度。 包含3个测试用例

在C语言中，我们可以使用动态规划(DP)的方法来解决最长单调递增子序列(LIS，Longest Increasing Subsequence)问题。以下是详细的步骤和一个示例代码：

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

// 定义函数来获取给定数组的LIS长度
int LIS(int arr[], int n) {
    // dp[i] 存储以arr[i]结尾的最长单调递增子序列长度
    int dp[n];
    // 初始化所有dp值为1，因为每个数都是它自身的单元素递增子序列
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }

    // 使用二维数组来存储两个相邻元素之间的最大递增长度
    int max_len = 1; // 初始最长子序列长度
    int temp_dp[n]; // 辅助数组用于查找更大的子序列

    // 遍历数组，对于每个元素，找到所有小于它的且能构成更大子序列的元素
    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; // 更新当前元素的最长递增子序列长度
                // 如果新长度比之前记录的最大长度还大，更新max_len
                if (dp[i] > max_len) {
                    max_len = dp[i];
                    temp_dp[i] = j; // 记录上一个元素的位置
                }
            }
        }
    }

    // 从temp_dp中回溯，构建最长递增子序列
    char *lis = (char*)malloc((max_len+1) * sizeof(char));
    lis[max_len] = '\0'; // 最后一个字符是'\0'
    int current_index = max_len;
    while (current_index != -1) {
        lis[current_index] = arr[temp_dp[current_index]];
        current_index = temp_dp[current_index];
    }

    printf("The longest increasing subsequence is: %s\n", lis);
    free(lis); // 释放内存
    return max_len;
}

// 测试用例
int main() {
    int test_cases[] = { {5, 4, 3, 2, 1}, {10, 9, 2, 5, 3, 7, 101, 18} , {1, 2, 3, 4, 5} };
    int sizes[] = {5, 8, 5};

    for (int i = 0; i < sizeof(test_cases)/sizeof(test_cases[0]); i++) {
        int n = sizes[i];
        int* arr = (int*)malloc(n * sizeof(int));
        memcpy(arr, test_cases[i], n * sizeof(int));
        printf("For array with elements: ");
        for (int j = 0; j < n; j++) {
            printf("%d ", arr[j]);
        }
        printf("\nLength of LIS: %d\n", LIS(arr, n));
        free(arr);
    }

    return 0;
}

在这个例子中，我们首先初始化一个长度为`n`的一维数组`dp`，其中`dp[i]`表示以`arr[i]`结尾的最长递增子序列长度。然后通过两层循环遍历数组，找出当前元素可以添加到哪些已经存在的递增子序列中，以增加子序列的长度。

当遍历结束后，我们有`dp`数组保存了所有元素的递增子序列长度，以及`temp_dp`数组记录了每个元素所属的最长子序列前一个元素的位置。最后，通过`temp_dp`回溯，构建出最长递增子序列并打印出来。

针对提供的三个测试用例，这个程序会计算并输出每个数组的最长递增子序列及其长度。