最长子列表算法 [英] The longest sublist algorithm

问题描述

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

I'm struggling with quite interesting assignment and looking for advice. The case is to find the longest sublist from the given list of pairs. First elements from these pairs should be in ascending order and second ones - in descending.

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

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

So, how I see this: Go via array and check condition for two pairs, if condition is true, save value somewhere and increase sublist elements count. Otherwise check if current sublist recording is empty and add the last element to current sublist, then check if this sublist is the longest among others. And I encountered two major problems - duplicates and absence of the last element.

此刻，我来到了这里：

     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 

预先感谢任何线索或提示。

Thanks in advance for any clue or hint.

推荐答案

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

I Wrote for you this algorithm it Does exactly what you want.

1）我创建了一个结果ArrayList;

1) i create a results ArrayList;

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

2) initialize variable sum to 0;

3）遍历 array [] []; 的所有值，获取每个数组值的总和

3) loop through all values of array[][]; for each array value get the sum of its components

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

4) if the sum of the components of thhe array value is less or equal to sum then insert the array value in the results array

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

5) but if the sum of the components of the array value is greater than sum, then check the results array. if its empty then insert the array value. if its not empty check the sum of the components of each value of the results Arraylist with the sum of the components of the value of the soucrce array.Any value with sum less than that of source array component is removed then insert this particular value to the results 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();
    }

}

输出为

3


4 4
5 3
6 2

这篇关于最长子列表算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！