最长子列表算法

小编典典

最长子列表算法

algorithm

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

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

因此，我的看法是：遍历数组并检查两对条件，如果条件为true，则将值保存在某处并增加子列表元素的数量。否则，检查当前子列表记录是否为空并将最后一个元素添加到当前子列表中，然后检查该子列表是否是最长的。我遇到了两个主要问题-
重复和缺少最后一个元素。

目前，我来到这里：

     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 + " ");

            }
        }
    }

输出：

在此先感谢您提供任何线索或提示。

阅读 265

2020-07-28

共1个答案

小编典典

我为您编写了此算法，它确实满足您的要求。

1）我创建一个结果ArrayList;

2）将变量sum初始化为0；

3）遍历所有array[][];数组的所有值，获取其组成部分的总和

4）如果数组值的组成部分之和小于或等于sum，则将数组值插入结果数组

5）但如果数组值的成分之和大于sum，则检查结果数组。如果为空，则插入数组值。如果它不是空的，则检查结果Arraylist的每个值的成分之和与源数组值的成分之和。任何总和小于源数组成分的值都将被删除，然后将该特定值插入到结果arraylist。

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();
    }

}

输出是

2020-07-28