The longest sublist algorithm

Question

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.

For example for {{1,3},{3,1},{2,0},{4,4},{5,3},{6,2}} answer is {{4,4},{5,3},{6,2}}

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.

For this moment I came to this:

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

            }
        }
    }

output:

2

1 3 
3 1 

Thanks in advance for any clue or hint.

Answer 1

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

1) i create a results ArrayList;

2) initialize variable sum to 0;

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

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

}

the output is

3


4 4
5 3
6 2

Answer 2

Okay, a hint first.

For every pair (x, y) for a given x, you're only interested in the one with the greatest y.

For every pair (x, y) for a given y, you're only interested in the one with the smallest x.

Try building maps of respective least/greater values for the x's and y's and see where you get from there (you will need two copies of the pair list, one sorted lexicographically x -> y and one sorted lexicographically y -> x).