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

Joop Eggen · Accepted Answer · 2016-08-08 16:05:16Z

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

edited Aug 8, 2016 at 16:05

answered Aug 8, 2016 at 13:59

Joop Eggen

110k8 gold badges89 silver badges142 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

Motombo Over a year ago

Heres the problem, I want to first find out which one has the most identical numbers, in your example 333333 count should be 6. But my count variable is resetting every time within the loop. How do I make it stop at the largest count in the sequence.

Motombo Over a year ago

Could you add some comments or explain a bit more about the details inside the for loop? I tried writing some stuff on paper, but I'm really lost now :/

Motombo Over a year ago

Particularly i < nums.size() - lengthBest.

Joop Eggen Over a year ago

@cresjoy That - lengthBest is not true! Thanks, Only when in the else-branch, when a new sequence starts, one could break out of the loop, when the remaining can never be longer than lengthBest. There are better optimizations possible.

Motombo Over a year ago

I noticed this puts brackets sometimes on our first character. For example I got this output (8)5267292485283145494

|

Chris · Accepted Answer · 2016-08-08 13:38:16Z

1

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.

answered Aug 8, 2016 at 13:38

Chris

8993 gold badges13 silver badges34 bronze badges

1 Comment

Motombo Over a year ago

I'm having trouble since my count always reset and is the same value as oldCount, could you look at my edited snippet

FruBlom · Accepted Answer · 2016-08-08 13:50:38Z

1

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.

answered Aug 8, 2016 at 13:50

FruBlom

231 silver badge8 bronze badges

1 Comment

Motombo Over a year ago

Yup im trying that but my count variable is resetting, see the examle I edited

Collectives™ on Stack Overflow

Find largest sequence within an arraylist

3 Answers 3

12 Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

12 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related