java - 在数组列表中查找最大序列

Question

一些背景

上周我在教科书上做了一道题，它告诉我生成 20 个随机数，然后用括号括起连续相等的数字 考虑以下我的程序输出

697342(33)(666)(44)69(66)1(88)

我需要做什么

下一个问题基本上是获取这些单词的最长序列并将它们括起来。如果你有

1122345(6666)

基本上，您需要将四个 6 放在方括号中，因为它们出现的频率最高。我已经完成了我正在学习的章节中的所有其他问题(Arrays 和 ArrayLists)，但是我似乎无法解决这一问题。

这是我为将连续数字放在方括号中而做出的解决方案:

class Seq
{
    private ArrayList<Integer> nums;
    private Random randNum;
    public Seq()
    {
        nums = new ArrayList<Integer>();
        randNum = new Random();
    }
    public void fillArrList()
    {
        for (int i = 0 ; i < 20 ; i++)
        {
            int thisRandNum = randNum.nextInt(9)+1;
            nums.add(thisRandNum);
        }
    }

    public String toString() {
        StringBuilder result = new StringBuilder();
        boolean inRun = false;
        for (int i = 0; i < nums.size(); i++) {
            if (i < nums.size() - 1 && nums.get(i).equals(nums.get(i + 1))) {
                if (!inRun) {
                    result.append("(");
                }
                result.append(nums.get(i));
                inRun = true;

            } else {
                result.append(nums.get(i));
                if (inRun) {
                    result.append(")");
                }
                inRun = false;

            }
        }
        return result.toString();
    }
}

我的想法

遍历整个列表。创建一个计数变量，跟踪有多少数字彼此连续。即 22 的计数为 2。 444 3 的计数接下来制作一个 oldCount，它将当前 count 与 oldCount 进行比较。如果我们的新 count 大于 oldCount

，我们只想继续前进

之后，我们需要一种方法来获取最大的 count 变量的起始索引以及结束。

我的思路对吗？因为我在比较 oldCount 和 count 变量时遇到问题，因为它们的值不断变化。 我不是在寻找代码，而是在寻找一些有值(value)的提示。

我的计数是这样重置的

int startIndex, endIndex = 0;
        int count = 0;
        int oldCount = 0;

            for(int i = 0 ; i < nums.size(); i++)
            {
                if(nums.get(i) == nums.get(i+1) && count >= oldCount)
                {
                    count++;
                }
                oldCount = count;
            }

Answer 1

只有遍历所有元素后，您才能知道最长的子序列。

11222333333444555
11222(333333)444555

因此只有在循环之后你才能插入两个括号。

所以你必须保持局部最优:起始索引加上长度或最优的最后一个索引。然后对于每个序列，当前序列的起始索引。

---

如问:

最优状态(序列)和当前状态是两个东西。不能事先说任何当前状态就是最终的最优状态。

public String toString() {
    // Begin with as "best" solution the empty sequence.
    int startBest = 0; // Starting index
    int lengthBest = 0; // Length of sequence

    // Determine sequences:
    int startCurrent = 0; // Starting index of most current/last sequence
    for (int i = 0; i < nums.size(); i++) {
        // Can we add the current num to the current sequence?
        if (i == startCurrent || nums.get(i).equals(nums.get(i - 1)))) {
            // We can extend the current sequence with this i:
            int lengthCurrent = i - startCurrent + 1;
            if (lengthCurrent > lengthBest) { // Current length better?
                // New optimum:
                startBest = startCurrent;
                lengthBest = lengthCurrent;
            }
        } else {
            // A different num, start here.
            // As we had already a real sequence (i != 0), no need for
            // checking for a new optimum with length 1.
            startCurrent = i;
        }
    }
    // Now we found the best solution.
    // Create the result:
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < nums.size(); i++) {
        result.append(nums.get(i));
    }
    // Insert the right ')' first as its index changes by 1 after inserting '('.
    result.insert(startBest + lengthBest, ")");
    result.insert(startBest, "(");
    return result.toString();
}

第一个问题是如何找到序列的结尾，并设置序列的正确起点。

原始算法的问题在于只处理了一个序列(一个子序列开始)。