Find the largest sequence of numbers in an integer array

Question

This is what I got so far. What I was trying to do was go through and find the sequence using a greater or equal value in the if statement. Then, when this value is no longer greater than or equal to the preliminary number, it goes into the else statement, which records this sequence number and resets it so that the count can start again. All of these sequence values ​​are stored in the arraylist, so when I'm done, I can just do a simple comparison to find the largest sequence number and return it. I need help with my first if / else statement, which collects sequence data, because I am sure that this is where my problems occur.

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 do not need to use a temporary list for this. Just loop the array or list using a counter and increment for each element that is greater than or equal to the previous one. Use another variable to keep 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 increase it while we are on a continuous / growing strip. As soon as this strip is broken (the else clause), we check whether count max greater than our variable to store the maximum value: if so, we set max to count . Then we set count back to 1, because in the else clause we know that our line has ended, and we will need to start all over again.

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

Answer 2

This can 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 LinkedList instances, it should work with any list.

Answer 3

This is similar to the answer from arshajii, but there is a fix suggested 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

To preserve the original data structures, I propose to solve this problem.

Parameter Testing:

 ArrayList<Integer> list = new ArrayList<Integer>(); list.add(12); list.add(12345); list.add(999999999); System.out.println(getMaxSequence(list)); 

Now I just compare all the values ​​with an index of 0, but absolutely not needed :)

 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 5

The longest growing subsequence problem is a dynamic programming problem that calculates the length of an nonadjacent 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 6

You can use compilations from java util and you can explicitly find it with arraylist.

 ArrayList<Integer> list = new ArrayList<Integer>(); // Here add data to ArrayList int maxNum = Collections.max(list); 

maxNum is the largest integer from the list.

Answer 7

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

1. Add all the integers from the list to the set.
2. Go through a lot.
3. Check for the presence of an element (element - 1) in the set. If so, proceed to the next iteration because this is not the beginning of the sequence.
4. Otherwise, in the while loop, check how many elements in sequence to the element are present in the collection.

An example program for the mentioned algorithm will look like this:

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