如何比较多组浮点型钻石重量、净度以求解最长优质子序列

• 该需求是经典双维度最长递增子序列（LIS）变种，核心要求子序列满足「重量严格递增 + 净度严格递减（即逐颗更优）」，无需暴力全量比对所有钻石组合，优化后时间复杂度可控制在O(n²)级别。
• 你当前代码的核心问题是未存储读取到的钻石属性，读完直接丢弃导致后续无法做跨钻石比对，需要先将每个测试用例的钻石数据存入集合再处理。

1. 定义钻石实体类存储单颗钻石的重量、净度属性
2. 对当前测试用例的所有钻石做排序：优先按重量升序排列，重量相同时按净度降序排列，避免同重量钻石被误加入同一条子序列
3. 定义dp数组，dp[i]表示以第i颗钻石为结尾的最长符合要求子序列的长度，状态转移规则为：如果第j颗钻石的重量小于第i颗、且净度大于第i颗，就可以把第i颗接在第j颗的子序列后面，即dp[i] = Math.max(dp[i], dp[j] + 1)
4. 遍历完所有钻石后，dp数组的最大值即为该测试用例的最长子序列长度

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Diamonds {

    // 钻石实体类存储属性
    static class Diamond {
        float weight;
        float clarity;

        public Diamond(float weight, float clarity) {
            this.weight = weight;
            this.clarity = clarity;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 获取测试用例总数
        int testCaseCount = scan.nextInt();

        for (int i = 0; i < testCaseCount; i++) {
            int diamondCount = scan.nextInt();
            List<Diamond> diamondList = new ArrayList<>();
            // 读取当前测试用例所有钻石数据
            for (int j = 0; j < diamondCount; j++) {
                float weight = scan.nextFloat();
                float clarity = scan.nextFloat();
                diamondList.add(new Diamond(weight, clarity));
            }

            // 排序规则：重量升序，同重量则净度降序
            diamondList.sort(Comparator.comparing((Diamond d) -> d.weight)
                    .thenComparing(d -> -d.clarity));

            int[] dp = new int[diamondCount];
            int maxLength = 1;
            // 初始化每个位置最短子序列长度为1（仅包含自身）
            for (int k = 0; k < diamondCount; k++) {
                dp[k] = 1;
                for (int l = 0; l < k; l++) {
                    // 满足重量严格递增、净度严格递减（更优）则更新状态
                    if (diamondList.get(l).weight < diamondList.get(k).weight
                            && diamondList.get(l).clarity > diamondList.get(k).clarity) {
                        dp[k] = Math.max(dp[k], dp[l] + 1);
                    }
                }
                maxLength = Math.max(maxLength, dp[k]);
            }
            // 输出当前测试用例结果
            System.out.printf("测试用例%d 最长符合要求的子序列长度：%d%n", i+1, maxLength);
        }
        scan.close();
    }
}

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