Wsrtjtyk

I am working on a program where I need to find out the maximum chain that can be formed from a given array.

Example:

Let's say input is :

Arr[0] = 5

Arr[1] = 4

Arr[2] = 0

Arr[3] = 3

Arr[4] = 1

Arr[5] = 6

Arr[6] = 2

Now if I take the array index and the corresponding value the possible max chain I can form is

index 0 with value 5 --> index 5 with value 6 --> index 6 with value 2 --> index 2 with value 0. This cycle repeats so this is my maximum chain i can form using this array

Here is my code:

public static int getMax(int nums) {

        int result = 0;

        for (int i = 0; i < nums.length; i++) {

            List<Integer> list = new ArrayList<>();

            list.add(i);

            int temp = i;

            while (true) {

                int next = nums[temp];

                if (list.contains(next)) {

                    break;

                } else {

                    list.add(next);

                    temp = next;

                }

            }

            result = Math.max(result, list.size());

        }

        return result;

    }

I have come up with above logic but I see that in my code I am trying to find multiple chains of the same type.

It means if I print my list it has these values:

[0, 5, 6, 2]

[1, 4]

[2, 0, 5, 6]

[3]

[4, 1]

[5, 6, 2, 0]

[6, 2, 0, 5]

Here 0,5,6,2 chain is repeated multiple times, is there a way to improve my code performance to avoid unnecessary similar loops like above.

You can put each values you get to an array by checking if that item is already contains in the array. Then when you iterate if you get a number in the array you filled, you can ignore that iteration by using continue

You can do it in two ways: you can make a list of used indices or you can create additional boolean array and there you can mark if this index was chosen. The second way is better, because you will not use a lot of additional memory, and also it will work faster. But the second way needs initialisation when first way does not.

each chain is a directed path. Then you have a Graph(v,e) with v as each index and e as a pair (v1, v2) such that exist A[v1]=v2. Then, you can identify a path as a set of e. Therefore you can check if you already have covered a path storing each e that you have covered and comparing them agains the new ones.

Like this:

    int nums = new int{5,4,0,3,1,6,2};

    int result = 0;

    List<String> coveredE = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {

        List<Integer> list = new ArrayList<>();

        list.add(i);

        int temp = i;

        // avoid covered edges

        if(coveredE.contains("("+temp+","+nums[temp]+")")) continue;

        while (true) {

            int next = nums[temp];

            // store covered edges

            coveredE.add("("+temp+","+next+")");

            if (list.contains(next)) {

                break;

            } else {

                list.add(next);

                temp = next;

            }

        }

        System.out.println(list);

        result = Math.max(result, list.size());

    }

    System.out.println(result);