java - 最长子列表算法

Question

我正在努力完成非常有趣的任务并寻求建议。 案例是从给定的对列表中找到最长的子列表。这些对中的第一个元素应按升序排列，第二个元素应按降序排列。

例如 {{1,3},{3,1},{2,0},{4,4},{5,3},{6,2}}答案是 {{4,4},{5,3},{6,2}}

所以，我是怎么看的: 通过数组并检查两对的条件，如果条件为真，则将值保存在某处并增加子列表元素数。否则检查当前子列表记录是否为空并将最后一个元素添加到当前子列表，然后检查该子列表是否是最长的。 我遇到了两个主要问题 - 重复和缺少最后一个元素。

为了这一刻，我来到了这里:

     public static void findLagrestList() {
        int arr[][] = {{1,3},{3,1},{2,0},{4,4},{5,3},{6,2}};

        ArrayList<int[]> currentSublist = new ArrayList<>();
        ArrayList<int[]> resultSublist = new ArrayList<>();

        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr[i].length-1; j++) {
                if (arr[i][j] < arr[i + 1][j] && arr[i][j + 1] > arr[i + 1][j + 1]) {
                    if(!currentSublist.contains(arr[i])){
                        currentSublist.add(arr[i]);
                    }

                } else {
                    currentSublist.add(arr[i]);//the last one
                    if(currentSublist.size()>resultSublist.size()){
                        resultSublist.clear();
                        resultSublist.addAll(currentSublist);
                        currentSublist.clear();
                    }

                    break;
                }
            }   
        }
System.out.println(resultSublist.size());
printList(resultSublist);

}

private static void printList(ArrayList<int[]> list) {

        for (int[] is : list) {
            System.out.println();
            for (int i : is) {
                System.out.print(i + " ");

            }
        }
    }

输出:

2

1 3 
3 1 

提前感谢您提供任何线索或提示。

Answer 1

我为您编写了这个算法，它完全符合您的要求。

1) 我创建一个结果 ArrayList；

2) 初始化变量sum为0；

3) 遍历 array[][]; 的所有值，为每个数组值获取其分量的总和

4) 如果数组值的分量之和小于或等于 sum 则将数组值插入结果数组

5) 但如果数组值的分量之和大于 sum，则检查结果数组。如果它为空，则插入数组值。如果它不为空，则检查结果 Arraylist 的每个值的分量之和与 soucrce 数组值的分量之和。删除总和小于源数组分量的任何值，然后将此特定值插入到结果数组列表。

import java.util.ArrayList;
class lists{
     public static void findLagrestList() {
            int arr[][] = {{1,3},{3,1},{2,0},{4,4},{5,3},{6,2}};

            //ArrayList<int[]> currentSublist = new ArrayList<>();
            ArrayList<int[]> resultSublist = new ArrayList<>();

            int result_arr[][]={};

            int sum =0;
            for(int i=0;i<arr.length;i++)
            {
                int [] inner_arr =arr[i];
                int valuesum =arr[i][0]+arr[i][1];
                if(valuesum>sum)
                {
                    if(resultSublist.size()>0)
                    {
                        for(int k=0;k<resultSublist.size();k++)
                        {
                            int [] cvalue = resultSublist.get(k);
                            int summ=cvalue[0]+cvalue[1];
                            if(valuesum>summ)
                            {
                               resultSublist.remove(k) ;
                            }

                        }
                        resultSublist.add(inner_arr);
                    }else{
                        resultSublist.add(inner_arr);
                        sum = valuesum;
                    }
                }
            }



System.out.println(resultSublist.size());
printList(resultSublist);

}

    private static void printList(ArrayList<int[]> list) {

        for (int[] is : list) {
            System.out.println();
            for (int i : is) {
                System.out.print(i + " ");

            }
        }
    }

    public static void main(String [] oo)
    {
         lists.findLagrestList();
    }

}

输出是

3


4 4
5 3
6 2