一个数组，抽出几个数，使得剩下的数组有序且最长，编程题 java

这是一个经典的动态规划问题——最长递增子序列（Longest Increasing Subsequence，简称 LIS）问题。

我们可以使用动态规划的思想来解决这个问题。设 dp[i] 表示以第 i 个数为结尾的 LIS 的长度。因为最长递增子序列的结尾必须是原序列中的一个数，所以我们可以枚举结尾的数，然后对于每个结尾，枚举它前面所有比它小的数，计算以这些数为结尾的 LIS 的长度，然后取最大值加 1 就是以当前数为结尾的 LIS 的长度。状态转移方程如下：

dp[i] = max{ dp[j] } + 1，其中 j < i 且 a[j] < a[i]。

最终的最长递增子序列的长度就是所有 dp[i] 中的最大值。如果我们需要输出具体的最长递增子序列，我们可以在计算 dp[i] 的同时，记录 dp[i] 的最优解的前一个数的下标。

以下是 Java 代码实现：

public static int[] findLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int[] prev = new int[n];
    Arrays.fill(prev, -1);
    int maxLen = 0, maxIdx = -1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            maxIdx = i;
        }
    }
    int[] lis = new int[maxLen];
    for (int i = maxIdx, j = maxLen - 1; i >= 0; i--) {
        if (dp[i] == j + 1) {
            lis[j--] = nums[i];
        }
    }
    return lis;
}

该函数接受一个整数数组 nums，返回一个最长递增子序列。如果有多个最长递增子序列，返回任意一个即可。