Найти наибольшую последовательность чисел в целочисленном arraylist

Это то, что я получил до сих пор. То, что я пытался сделать, это пройти и найти последовательность, используя больше или равно тоже в операторе if. Затем, когда это значение больше не больше или равно предыдущему числу, оно переходит в оператор else, который записывает этот порядковый номер и сбрасывает его, чтобы счетчик мог начать снова. Все эти значения последовательности сохраняются в arraylist, так что когда я все сделаю, я могу просто сделать простое сравнение, чтобы найти наибольшее порядковое число и вернуться тот. Мне нужна помощь с моим первым заявлением if/else, которое собирает данные последовательности, потому что я уверен, что именно здесь происходят мои проблемы. 

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;
    }
7 6
arraylist sequences

7 ответов:

Для этого не нужно использовать временный список. Просто выполните цикл по массиву или списку со счетчиком и приращением для каждого элемента, который больше или равен предыдущему. Используйте другую переменную для хранения максимума: 

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

Здесь count - число смежных и отсортированных элементов. Мы увеличиваем его, пока находимся на непрерывной / возрастающей полосе. Как только эта полоса прерывается (else предложение), мы проверяем, если count больше, чем max, наша переменная для хранения максимальное число: если это так, мы устанавливаем max в count. Затем мы возвращаем count к 1, так как в предложении else мы знаем, что наша полоса закончилась, и нам нужно будет начать все сначала.

(я использовал массив здесь, но он должен быть тривиальным, чтобы преобразовать приведенный выше код для работы со списками).

7

Это можно сделать рекурсивно: 

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

И используется так: 

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

Хотя он должен быть быстрее с экземплярами LinkedList, он должен работать с любым списком.

1

Это похоже на ответ из arshajii, но имеет исправление, предложенное для того, когда последовательность находится в конце массива. Этот ответ также проверяет монотонно возрастающие или равные числа.

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

Ради сохранения первоначально использованных структур данных-вот как я предложил бы решить эту проблему.

Параметры тестирования: 

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

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

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

Теперь я просто сравниваю все значения с indx 0, но совершенно не обязательно :) 

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;

}
0

Вы можете использовать следующий алгоритм для получения наибольшей последовательности целых чисел, присутствующих в любом заданном ArrayList.

  1. Добавьте все целые числа из списка в набор.
  2. перебирайте множество.
  3. Проверьте наличие элемента, если (элемент - 1) присутствует в наборе. Если да, то переходите к следующей итерации.
  4. иначе, в цикле while проверьте, сколько элементов подряд к элементу присутствуют в наборе.

Пример программы для упоминания algo будет выглядеть например: 

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)) {
                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;
    }
}
0

Самая длинная задача возрастающей подпоследовательности-это задача динамического программирования, которая вычисляет длину несмежной подпоследовательности из заданной последовательности 

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

Вы можете использовать коллекции из самого Java util и можете найти из arraylist явно.

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

// Here add data to ArrayList

int maxNum =  Collections.max(list);

MaxNum-самое большое целое число из списка.

-1