Find largest sequence within an arraylist

Question

Some Background

Last week I did a problem in my textbook where It told me to generate 20 random numbers and then put brackets around successive numbers that are equal Consider the following which my program outputs

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

What I need to do

The next problem was to basically get the longest sequence of these words and put brackets around them. If you have

1122345(6666)

Basically you need to put brackets around four 6's , since they occur most often. I've finished all other problems in the chapter I am studying ( Arrays and ArrayLists), however I can't seem to figure this one out.

Here is the solution that I have made for putting brackets around successive numbers:

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

My Thoughts

Iterate through the whole list. Make a count variable, that keeps track of how many numbers are successive of each other. I.e 22 would have a count of 2. 444 a count of 3 Next make an oldCount, which compares the current count to the oldCount. We only want to keep going if our new count is greater than oldCount

After that we need a way to get the starting index of the largest count variable, as well as the end.

Is my way of thinking correct? Because I'm having trouble updating the oldCount and count variable while comparing them, since there values constantly change. I'm not looking for the code, but rather some valuable hints.

My count is resetting like this

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

Only after walking all elements you will know the longest subsequence.

11222333333444555
11222(333333)444555

Hence only after the loop you can insert both brackets.

So you have to maintain a local optimum: start index plus length or last index of optimum. And then for every sequence the start index of the current sequence.

---

As asked:

The optimal state (sequence) and the current state are two things. One cannot in advance say that any current state is the final optimal state.

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

The first problem is how to find the end of a sequence, and set the correct start of the sequence.

The problem with the original algorithm is that there is handled just one sequence (one subsequence start).

Answer 2

I think you need to iterate the entire list even though the current count is lower than the oldCount, what about e.g. 111224444?

Keep 4 variables while iterating the list: highestStartIndex, highestEndIndex, highestCount and currentCount. Iterate the entire list and use currentCount to count equal neighbouring numbers. Update the highest* variables when a completed currentCount is higher than highestCount. Lastly write the numbers out with paranthesis using the *Index variables.

Answer 3

The way you have suggested could work. And then, if newcount is greater than oldcount, you'll want to store an additional number in another variable - the index of the where the longest sequence begins.

Then later, you can go and insert the ( at the position of that index.

i.e. if you have 11223456666.

The biggest sequence starts with the first number 6. That is at index 7, so store that 7 in a variable.