从数组中找到元素的最大长度

Question

我正在开发一个程序，需要找出给定数组中可以形成的最大链条。

例如：

假设输入为：

Arr[0] = 5
Arr[1] = 4
Arr[2] = 0
Arr[3] = 3
Arr[4] = 1
Arr[5] = 6
Arr[6] = 2

现在，如果我取数组索引和相应的值，我可以形成的最大链是：

索引0，值为5 -> 索引5，值为6 -> 索引6，值为2 -> 索引2，值为0。这个循环重复，所以这是我使用这个数组可以形成的最大链。

以下是我的代码：

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

我想出了上述逻辑，但是我发现在我的代码中我正在尝试查找多个相同类型的链。这意味着如果我打印我的列表，它会有这些值：

[0, 5, 6, 2]
[1, 4]
[2, 0, 5, 6]
[3]
[4, 1]
[5, 6, 2, 0]
[6, 2, 0, 5]

这里重复多次使用了 0,5,6,2 链，有没有办法提高代码性能，避免不必要的类似循环？

- learner

---

术语方面，这种大小为n且包含n个不同整数的数组被称为排列，而你所说的“链”则是一个循环。 - David Soroko

Answer 1

您可以通过检查该项是否已包含在数组中，将获得的每个值放入数组中。然后，在迭代时，如果您在填充的数组中获得一个数字，则可以使用continue忽略该迭代。

- Sandeepa

Answer 2

每个链都是一个有向路径。那么你就有了一个 Graph(v,e)，其中 v 是每个索引，e 是一对 (v1,v2)，使得存在 A[v1]=v2。然后，你可以将路径标识为一组 e。因此，你可以检查是否已经覆盖了一条路径，存储每个已经覆盖的 e 并将其与新的进行比较。像这样：

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

- elbraulio

Answer 3

你可以用两种方法来实现：一种是创建已使用索引的列表，另一种是创建额外的布尔数组，并在其中标记是否选择了该索引。第二种方法更好，因为你不需要使用大量的额外内存，而且它也会更快。但第二种方法需要初始化，而第一种方法则不需要。

- Dima Rich