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

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

Answer 2

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.

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

Answer 4

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

Answer 5

For the sake of keeping the data structures originally used-- this is how I would propose solving this issue.

Testing params:

ArrayList<Integer> list = new ArrayList<Integer>();

list.add(12);
list.add(12345);
list.add(999999999);

System.out.println(getMaxSequence(list));

Now, I simply compare all the values to indx 0, but totally not necessary :)

public static int getMaxSequence(ArrayList<Integer> list) {

    int indx = 0;
    int currmax = 0;
    currmax = list.get(indx).toString().length();
    while (indx < list.size()) {

        if (currmax <= list.get(indx).toString().length()) {
            currmax = list.get(indx).toString().length();
        } else
            return currmax;

        // list.remove(indx);
        indx++;

    }

    return currmax;

}

Answer 6

The longest increasing subsequence problem is a dynamic programming problem that calculates the length of a non-contiguous subsequence from a given sequence

import java.io.*;
public class CandidateCode 
{ 
public static int longestSeq(int[]seq){
int[]L=new int[seq.length];
L[0]=1;
for(int i=1;i<L.length;i++){
int maxn=0;
for(int j=0;j<i;j++){
if(seq[j]<seq[i]&&L[j]>maxn){
maxn=L[j];
}
}
L[i]=maxn+1;
}
int maxi=0;
for(int i=0;i<L.length;i++){
if(L[i]>maxi){
maxi=L[i];
}
}
return(maxi);
}
}

Answer 7

You can use Collections from java util itself and can find from arraylist explicitly.

ArrayList<Integer> list = new ArrayList<Integer>();

// Here add data to ArrayList

int maxNum =  Collections.max(list);

maxNum is Biggest integer from a list.