7

这是我到目前为止所得到的。我试图做的是在 if 语句中使用更大或等于来查找序列。然后，当该值不再大于或等于先前的数字时，它进入 else 语句，该语句记录该序列号并重置它，以便重新开始计数。所有这些序列值都保存在一个数组列表中，所以当我完成后，我可以做一个简单的比较来找到最大的序列号并返回它。我需要关于收集序列数据的第一个 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;
    }
4

7 回答 7

9

您不必为此使用临时列表。只需使用计数器循环遍历数组或列表，并为每个大于或等于前一个的元素递增。使用另一个变量来存储最大值：

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子句中我们知道我们的连胜已经结束，我们需要重新开始。

（我在这里使用了一个数组，但是将上面的代码转换为使用列表应该很简单）。

于 2013-09-25T01:27:21.687 回答
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));
于 2015-04-30T08:47:01.253 回答
1

它可以递归地完成：

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 的实例应该更快，但它应该适用于任何列表。

于 2013-09-25T02:10:20.413 回答
1

您可以使用以下算法来获取任何给定 ArrayList 中存在的最大整数序列。

  1. 将列表的所有整数添加到集合中。
  2. 迭代集合。
  3. 如果 (element - 1) 存在于 Set 中，则检查该元素。如果是，则继续下一次迭代，因为它不是序列的开始。
  4. 否则，在一个 while 循环中，检查 Set 中有多少与元素连续的元素。

提及算法的示例程序如下所示：

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;
    }
}
于 2018-03-18T17:04:36.137 回答
0

为了保留最初使用的数据结构——这就是我建议解决这个问题的方式。

测试参数：

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;

}
于 2013-09-25T02:12:29.937 回答
-1

最长递增子序列问题是一个动态规划问题，它计算给定序列的非连续子序列的长度

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);
}
}
于 2014-03-23T11:17:50.817 回答
-1

您可以使用 java util 本身的 Collections，并且可以显式地从 arraylist 中找到。

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

// Here add data to ArrayList

int maxNum =  Collections.max(list);

maxNum 是列表中的最大整数。

于 2015-06-02T05:59:13.113 回答