寻找Java数组中最长的向下序列

Question

给定这个数组，

int [] myArray = {5,-11,2,3,14,5,-14,2};

我必须能够返回 3，因为最长的向下序列是 14,5,-14。 最快的方法是什么？

PS：下降序列是一系列不递增的数字。

Answer 1

python 中的另一个实现：

def longest_down_sequence(seq):
    max = 0
    current_count = 0
    last = None
    for x in seq:
        if x <= last: current_count += 1
        else: current_count = 1
        if current_count > max: max = current_count
        last = x
    return max

Answer 2

只需浏览一下数字列表即可。伪代码：

bestIndex = 0
bestLength = 0

curIndex = 0
curLength = 1

for index = 1..length-1
   if a[index] is less than or equal to a[index-1]
       curLength++
   else 
       //restart at this index since it's a new possible starting point
       curLength = 1
       curIndex = index

   if curLength is better than bestLength
       bestIndex = curIndex
       bestLength = curLength

next          

注意：如果您不关心知道子序列发生的位置，则可以放弃包含 bestIndex 或 curIndex 的任何行，如 Gary 的实现中所示。

Answer 3

在java中：

    int [] myArray = {5,-11,2,3,14,5,-14,2};
    int downSequence = 1;
    int longestDownSequence = 1;
    for(int i = 1; i < myArray.length; i++) {
        if(myArray[i] <= myArray[i-1]) downSequence++;
        else {
            if(downSequence > longestDownSequence)
                longestDownSequence = downSequence;
            downSequence = 1;
        }
    }
    if(downSequence > longestDownSequence)
        longestDownSequence = downSequence;
    System.out.println(longestDownSequence);

由于您要求最快或更好的性能，因此仅在重置计数器之前检查最长的下降序列。永远不会在每次迭代中。但是，您必须在循环后再次检查，以防最长的序列位于数组的末尾。

Answer 4

Java中的另一种解决方案：

static int[] longestDownSequenceList(int[] array) {

    if (array.length <= 1) {
        return array;
    }

    int maxSize = 1; 
    int maxEnd = 0; 

    int curSize = 1;

    for (int i = 1; i < array.length; i++) {

        if (array[i] < array[i-1]) {
            curSize++;

            if (curSize > maxSize) {
                maxSize = curSize; 
                maxEnd = i;
            }
        }
        else {               
            curSize = 1;
        }
    }

    return Arrays.copyOfRange(array, maxEnd-maxSize+1, maxEnd+1);
}

Answer 5

正如比尔上面所说，这本质上是最长的递增子序列。请参阅维基百科条目以获取最佳解决方案。这是从那里引用的，进行了一些小的更改，以适用于非递减的情况，

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L such that X[M[j]] >= X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] >= X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)

请参阅上面我的评论中其他提议的解决方案的反例。

Answer 6

最快的方法可能取决于环境：计算机和问题大小。

对于非常大的列表（或数组），并行化作业可能很有用，可以实现：

• 将列表拆分为简单元素。
• 将按顺序排列（或不增加）的元素粘合在一起，形成块，如果可能的话，将块粘合在一起。
• 搜索最长的块。