查找时间最长的连续子序列
问题描述:
我试图编写一个程序,将一个序列作为一个数组,然后打印最长的连续子序列以及其长度。在我迄今为止所写的代码中,我已经设法在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] + ", ");
}
}
}
答
只是为了澄清..为什么你不能采取最长的前进和扭转呢?最长的前锋会不会是最长的后卫的相反?
答
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]。
+0
我相信这应该是正确的答案,任何人都可以确认这一点。 – 2015-08-31 04:49:33
您是指按升序排列最长的数字序列? – erencan 2015-02-24 19:56:15
只需将阵列放在镜子上即可。 (只是为了混淆事情:平均来说,可能会比O(N)做得更好,但可能不如O(log N)。) – 2015-02-24 19:58:19