Find the largest sequence of numbers in an integer arraylist

Question

This is what I've gotten so far. What I've tried to do is go through and find the sequence using greater or equals too in an if statement. Then when that value no longer is greater or equal to the preveious number it goes into the else statement which records that sequence number and resets it so the count can begin again. All these sequence values are saved in an arraylist so that when I'm all done I can just do a simple comparison to find the greatest sequence number and return that. I need help with my first if/else statement that gathers the sequence data because I'm pretty sure this is where my issues are happening.

public class LongestSequence {

    public static int getMaxSequence(ArrayList<Integer> list) {
        int sequence = 0;
        ArrayList<Integer> temp = new ArrayList<Integer>();

        for (int i = 0; i < list.size() - 1; i++) {
            //this is where things go wrong. I think.
            if (list.get(i + 1) >= list.get(i)) {
                sequence++;
            } else {
                //record the number in your arraylist
                temp.add(sequence);
                //reset count to 0
                 sequence = 0;
            }
         }

        int greatestnum = 0;

        for (int i = 0; i < temp.size() - 1; i++) {
            if (temp.get(i) < temp.get(i + 1)) {
                greatestnum = temp.get(i + 1);
            } else {
                greatestnum = temp.get(i);
            }
        }
        return greatestnum;
    }

Solution 1

You shouldn't have to use a temporary list for this. Just loop through the array or list with a counter and increment for each element that is greater than or equal to the previous. Use another variable to store the maximum:

int[] a = { 1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3, 2 };

int count = 1, max = 1;

for (int i = 1; i < a.length; i++) {
    if (a[i] >= a[i - 1]) {
        count++;
    } else {
        count = 1;
    }

    if (count > max) {
        max = count;
    }
}

System.out.println(max);

6

Here, count is the number of contiguous and sorted elements. We increment it while we're on a continuous/increasing streak. Once this streak breaks (else clause), we check if count is greater than max, our variable for storing the maximum count: if it is, we set max to count. We then set count back to 1, since in the else clause we know our streak has ended and we'll need to start over.

(I've used an array here, but it should be trivial to convert the above code to work with lists).

Solution 2

You can use the following algorithm to get the largest sequence of Integers present in any given ArrayList.

1. Add all the Integers of the List to a Set.
2. Iterate over the Set.
3. Check for the element if (element - 1) is present in the Set. If yes, continue to the next iteration because it is not the start of the sequence.
4. Else, in a while loop check how many elements in succession to the element are present in the Set.

A sample program for the mention algo will look like:

package org.practice.algorithms.arrays;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LargestSequence {

    public Integer[] getLargestSequence(Integer[] numberArray) {

        List<Integer> largestSequence = new ArrayList<Integer>();
        int largestSequenceCount = 0;

        Set<Integer> numbersSet = getSetFromArray(numberArray);

        for (Integer integer : numbersSet) {
            if(numbersSet.contains(integer -1)) {
                //this number is not the start of the sequence.
                continue;
            } else {
                int count = 0;
                List<Integer> largestSequenceTemp = new ArrayList<Integer>();
                while(numbersSet.contains(integer)) {
                    largestSequenceTemp.add(integer);
                    integer++;
                    count++;
                }
                if(count > largestSequenceCount) {
                    largestSequenceCount = count;
                    largestSequence = largestSequenceTemp;
                }
            }

        }
        return largestSequence.toArray(new Integer[largestSequence.size()]);
    }

    private Set<Integer> getSetFromArray(Integer[] numberArray) {
        Set<Integer> numbersSet = new HashSet<Integer>();
        if(null != numberArray && numberArray.length > 0) {
            for (int number : numberArray) {
                numbersSet.add(number);
            }
        }
        return numbersSet;
    }
}

Solution 3

This is similar to the answer from arshajii but has the fix suggested for when the sequence is at the end of the array. This answer also checks for monotonically increasing or equal numbers.

https://jsfiddle.net/ppy6tdt8/

var a = [ 1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3, 2 ];
var b = [1,2,4,5,7,8,9];

function getSpan ( a ) {

if (a.length < 2) {
    return 1;
}

var count = 1, max = 1;

for (var i = 1; i < a.length; i++) {
    if (a[i] == a[i - 1]+1 || a[i] == a[i - 1]) {
        if (++count > max) {
            max = count;
        }
    } else {
        count = 1;
    }
}
return ( max );
}

console.log (getSpan(a));
console.log (getSpan(b));

Solution 4

It may be done recursively :

public static int getMaxSequence(List<Integer> list){
  if (list == null) return 0;
  if (list.size() == 1) return 1;

  return getMaxSequence(list.get(0), list.subList(1, list.size()),1);
}

public static int getMaxSequence(int head, List<Integer> tail,int soFar) {

  if (tail == null) return 0;
  if (tail.size()==0) return soFar;

  if (head <= tail.get(0)){
    soFar++; //the sequence gets bigger
  }else{
    soFar = 1; //restart the sequence
  }

  final int nextSeq = getMaxSequence(tail.get(0),tail.subList(1, tail.size()),soFar);

  //finally return what we have found so far or the longest sequence down the list
  return Math.max(soFar, nextSeq);      
}

And used like this :

final List<Integer> list = Arrays.asList(1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3, 2);
System.out.println(getMaxSequence(list));

Although it should be faster with instances of LinkedList, it should work with any List.

View more solutions

Comments

[Java Devil]

+1 My thoughts exactly, other than the use of array instead of a List

[Admin]

This is a lot simpler then I was trying. Thank you.

[Java Devil]

This doesn't answer the question, this function returns the length of the longest number until a shorter number is reached...

[Roberto Navarro]

So why did this get down voted? Maybe I misunderstood the problem?

[ibtarek]

@JavaDevil indeed. I have fixed it.

[Mike Valenty]

This algorithm doesn't count the last element of the array. For example { 1, 2, 3, 4, 0, 19, 1, 1, 2, 2, 3, 3} should also return 6, but it only returns 5. The fix is to check for max in the same block as incrementing the count.

[Amos M. Carpenter]

Welcome to SO, Barry. Please note that the order of answers may change depending on votes, so "answer 2 above" is not always going to be the same ;-)

[Barry Keepence]

Thank you for the welcome - I have used SO for a long time so I thought it was really time to give back.

[Amos M. Carpenter]

No worries - edit your answer to replace "answer 2 above" with something that lets people know which one you mean, and you'll get your first upvote ;-)

[madhu_karnati]

@arshajii your logic not working . My array is {1,2,4,5,3,6,7,8,9,10} . Longest possible sequence is 3,6,7,8,9,10. it is 6 count. But your logic giving me 4