查找时间最长的连续子序列

我试图编写一个程序，将一个序列作为一个数组，然后打印最长的连续子序列以及其长度。在我迄今为止所写的代码中，我已经设法在longestForward方法中完成了这个工作。然而，在赋值规范中，我也被要求写另一个方法longestBackwards，它完成了完全相同的任务，即。将打印完全相同的东西，但它必须向后搜索原始数组。这是我遇到困难的地方。我已经写了一个方法，只打印最长的连续子序列的最后两个成员，并以相反的顺序（例如，对于数组4,5,6打印6,5）。但它确实打印的长度。查找时间最长的连续子序列

如果有人可以帮助弄清楚我做了什么错误，将不胜感激。

import java.util.Scanner; 
public class LongestSubsequence { 
public static void main(String[] args) { 

    // Test array 
    int[] arr = {4, 5, 6}; 


    longestForward(arr); 
    longestBackward(arr); 

    } 

public static void longestForward(int[] arr) 
{ 
    int subSeqLength = 1; 
    int longest = 1; 
    int indexStart = 0; 
    int indexEnd = 0; 

    for (int i = 0; i < arr.length - 1; i++) 
    { 
     if (arr[i] < arr[i + 1])//We need to check if the current is equal to the next 
     { 
      subSeqLength++;//if it is we increment 
      if (subSeqLength > longest)//we assign the longest and new bounds 
      { 
       longest = subSeqLength; 
       indexStart = i + 2 - subSeqLength; 
       indexEnd = i + 2; 
      } 

     } 
     else 
      subSeqLength = 1;//else re-initiate the straight length 
    } 

System.out.println(longest); 
    for (int i = indexStart; i < indexEnd; i++)//print the sequence 

     System.out.print(arr[i] + ", "); 
} 
public static void longestBackward(int[] arr) { 

    int subSeqLength = 1; 
    int longest = 1; 
    int indexStart = 0; 
    int indexEnd = 0; 
    for (int i = arr.length - 1; i > 0; i--) { 
     if (arr[i] > arr[i - 1]) { 
      subSeqLength++; 
      if (subSeqLength > longest) { 
       longest = subSeqLength; 
       indexStart = i + (subSeqLength - 1); 
       indexEnd = i - 1; 
      } 
     } // Else re-initiate the length 
     else { 
      subSeqLength = 1; 
     } 
    } 
System.out.println(""); 
    // Print the sequence 
System.out.println(longest); 
    for (int i = indexStart-1; i > indexEnd; i--) { 
     System.out.print(arr[i] + ", "); 
    } 
} 
}

来源

2015-02-24 jofl

您是指按升序排列最长的数字序列？ – erencan 2015-02-24 19:56:15

只需将阵列放在镜子上即可。（只是为了混淆事情：平均来说，可能会比O（N）做得更好，但可能不如O（log N）。） – 2015-02-24 19:58:19

只是为了澄清..为什么你不能采取最长的前进和扭转呢？最长的前锋会不会是最长的后卫的相反？

来源

2015-02-24 19:40:41

哦，我认为这是可行的，只要因为我创建了一个简单地反转元素的新数组。我会怎么做呢？ – jofl 2015-02-24 19:45:50

http://stackoverflow.com/a/2138004/3897302 – 2015-02-24 19:47:20

等等，我现在很困惑。我是否简单地颠倒了最后找到的数组（现在仍然缺少一个数字），还是现在有一个非常简单的最长背包？请记住，longestBackwards需要打印与longestForwards相同的数组。 – jofl 2015-02-24 19:57:51

for (int i = arr.length - 1; i > 0; i--) { 
    if (arr[i] > arr[i - 1]) { 
     subSeqLength++; 
     if (subSeqLength > longest) { 
      longest = subSeqLength; 
      indexStart = i + (subSeqLength - 1); 
      indexEnd = i - 1; 
     } 
    } // Else re-initiate the length

不应该for循环看起来更像这个有点：

for (int i = arr.length - 1; i >= 0; i--) {

你没有得到ARR [0]，因为你改编后停止[1]。

来源

2015-02-24 20:10:12 Araymer

我相信这应该是正确的答案，任何人都可以确认这一点。 – 2015-08-31 04:49:33

查找时间最长的连续子序列

回答

相关问题