使用java实现N个元素的整数序列,如果从中挑选出一些元素组成一个严格递增的序列,元素保持原先后相对次序,写一个算法求这样的序列的最大长度

思路：

动态规划，设dp[i]为以第i个元素结尾的最长严格递增子序列的长度，那么dp[i]的值为前面所有比第i个元素小的元素的dp值加1的最大值。

代码实现：

public static int longestIncreasingSubsequence(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int res = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        res = Math.max(res, dp[i]);
    }
    return res;
}

时间复杂度：$O(n^2)$

相关问题

求一个由n个整数组成的整数序列的最长递增子序列过程代码

以下是使用动态规划求解最长递增子序列的代码：

def longest_increasing_subsequence(nums):
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

其中，nums是一个长度为n的整数序列，dp[i]表示以第i个数为结尾的最长递增子序列长度。遍历前面的所有数j，如果第j个数小于第i个数，那么以第j个数为结尾的最长递增子序列长度加1就是以第i个数为结尾的最长递增子序列长度，取最大值更新dp[i]。最终结果为dp数组中的最大值。

根据一个递增的整数序列构造有序单链表，删除其中的重复元素

可以按照以下步骤构造有序单链表并删除重复元素：

1. 定义一个链表节点结构体，包含一个整型数据域和一个指向下一个节点的指针域。

2. 读入递增的整数序列，依次创建链表节点，并将节点插入链表中，保证链表始终有序。

3. 遍历链表，对于每个节点，判断它的数据域是否与下一个节点的数据域相同，如果相同，则删除下一个节点，并将当前节点的指针域指向下一个节点的下一个节点。

4. 重复步骤3，直到遍历到链表末尾。

5. 返回删除重复元素后的链表头节点。

具体实现可以参考以下代码：

#include <iostream>
using namespace std;

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* deleteDuplicates(ListNode* head) {
    if (head == NULL) return NULL;
    ListNode* cur = head;
    while (cur->next != NULL) {
        if (cur->val == cur->next->val) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    return head;
}

int main() {
    // 读入递增的整数序列
    int n;
    cin >> n;
    ListNode* head = NULL;
    for (int i = ; i < n; i++) {
        int x;
        cin >> x;
        ListNode* node = new ListNode(x);
        if (head == NULL) {
            head = node;
        } else {
            ListNode* cur = head;
            while (cur->next != NULL && cur->next->val < x) {
                cur = cur->next;
            }
            node->next = cur->next;
            cur->next = node;
        }
    }
    // 删除重复元素
    head = deleteDuplicates(head);
    // 输出链表
    ListNode* cur = head;
    while (cur != NULL) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
    return ;
}