将文件空格分隔值存入多维数组并实现最长上升子序列算法

我来帮你一步步搞定这两个问题：先把文件数据正确读到结构里，再实现最长上升子序列的算法。

一、修正文件读取逻辑，灵活存储列数据 #

先看你现有代码里的几个小问题：

• 硬编码循环101次读行，如果文件实际只有50列，会直接抛出NoSuchElementException
• 用Integer.parseInt但数组是double类型，类型匹配没必要绕弯，直接用Double.parseDouble更合适
• StringTokenizer可以换成更简洁的split()方法，处理空格分隔更直观
• 固定大小的二维数组不够灵活，因为每列的元素个数可能不一样

这里是修正后的代码，我加了详细注释：

import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class LISProcessor {
    public static void main(String[] args) {
        // 用嵌套List存储，适配每列元素数量不同的情况，比固定二维数组更灵活
        List<List<Double>> columnsData = new ArrayList<>();

        try {
            System.out.print("Enter the file name with extension : ");
            Scanner input = new Scanner(System.in);
            File file = new File(input.nextLine());
            input = new Scanner(file);

            // 逐行读取文件，每行对应一列数据
            while (input.hasNextLine()) {
                String line = input.nextLine().trim();
                // 跳过空行，避免无效数据
                if (line.isEmpty()) continue;

                // 按任意数量的空格分割成数字字符串
                String[] numStrs = line.split("\\s+");
                List<Double> currentColumn = new ArrayList<>();
                for (String numStr : numStrs) {
                    currentColumn.add(Double.parseDouble(numStr));
                }
                columnsData.add(currentColumn);
            }
            input.close();

            // 测试输出：打印读取到的所有列数据
            System.out.println("读取完成，列数据如下：");
            for (int colIdx = 0; colIdx < columnsData.size(); colIdx++) {
                System.out.printf("第%d列：%s%n", colIdx + 1, columnsData.get(colIdx));
            }

            // 对每列计算最长上升子序列
            for (int colIdx = 0; colIdx < columnsData.size(); colIdx++) {
                List<Double> column = columnsData.get(colIdx);
                int lisLength = findLISLength(column);
                List<Double> lisSequence = findLISSequence(column);
                System.out.printf("第%d列的最长上升子序列长度：%d，序列为：%s%n",
                        colIdx + 1, lisLength, lisSequence);
            }

        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    // --- 下面是最长上升子序列的实现方法 ---
}

二、实现最长上升子序列（LIS）算法 #

你说的“无需替换元素的最长递增数字序列”就是标准的最长上升子序列（Longest Increasing Subsequence, LIS），我给你两种实现：一种是高效计算长度的O(n log n)算法，另一种是能输出具体序列的实现。

1. 高效计算LIS长度（O(n log n)） #

这个算法用辅助数组维护当前最长上升子序列的最小末尾元素，通过二分查找优化时间复杂度：

private static int findLISLength(List<Double> sequence) {
    if (sequence.isEmpty()) return 0;

    List<Double> tails = new ArrayList<>();
    tails.add(sequence.get(0));

    for (int i = 1; i < sequence.size(); i++) {
        double num = sequence.get(i);
        // 当前数比tails最后一个元素大，直接加入
        if (num > tails.get(tails.size() - 1)) {
            tails.add(num);
        } else {
            // 二分查找找到第一个大于等于当前数的位置，替换它
            int left = 0, right = tails.size() - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (tails.get(mid) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails.set(left, num);
        }
    }
    return tails.size();
}

2. 输出具体LIS序列 #

如果需要得到完整的最长上升子序列，我们需要额外记录每个元素的前驱索引，通过回溯得到序列：

private static List<Double> findLISSequence(List<Double> sequence) {
    if (sequence.isEmpty()) return new ArrayList<>();

    int n = sequence.size();
    // tails[i]表示长度为i+1的LIS的最小末尾元素的索引
    int[] tails = new int[n];
    // prev[i]记录sequence[i]在LIS中的前一个元素索引
    int[] prev = new int[n];
    // 初始化前驱索引为-1
    for (int i = 0; i < n; i++) {
        prev[i] = -1;
    }

    int length = 1;
    tails[0] = 0;

    for (int i = 1; i < n; i++) {
        double num = sequence.get(i);
        // 当前数比tails最后一个元素大，追加到tails末尾
        if (num > sequence.get(tails[length - 1])) {
            prev[i] = tails[length - 1];
            tails[length++] = i;
        } else {
            // 二分查找替换位置
            int left = 0, right = length - 1;
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (sequence.get(tails[mid]) < num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            tails[left] = i;
            if (left > 0) {
                prev[i] = tails[left - 1];
            }
        }
    }

    // 回溯得到LIS序列
    List<Double> lis = new ArrayList<>();
    int currentIdx = tails[length - 1];
    while (currentIdx != -1) {
        lis.add(sequence.get(currentIdx));
        currentIdx = prev[currentIdx];
    }
    // 反转得到正序的LIS
    java.util.Collections.reverse(lis);
    return lis;
}

测试你的示例数据 #

你提供的那串空格分隔的数字，只要把它保存成文件里的一行（作为一列），运行代码就能得到结果。比如这串数据的LIS长度是28，具体序列会包含-31, -21, 30, ..., 48这类递增元素。

内容的提问来源于stack exchange，提问作者Bestils