计算数组中最长有序子序列的长度

我正在浏览https://projecteuler.net/等网站，我遇到了这个问题：

“给定长度为N> 0的无序数组，计算数组中最长有序（从左[下部索引]到右部[更高索引]）子序列的长度。”

对于我的生活，我很难找到Java解决方案。 有人可以帮忙吗？

编辑：

一些例子：

例1

输入：[1,4,1,4,2,1,3,5,6,2,3,7]预期输出：4

例2

输入：[3,1,4,1,5,9,2,6,5,3,5]预期输出：3

例3

输入：[2,7,1,8,2,8,1]预期输出：2

Answer 1

你想要找到的术语是一个子arrays，而不是一个子序列（根据你的例子）。 您可以使用简单的循环在线性时间内解决它：

int res = 0; int cur = 0; for (int i = 0; i < a.length; i++) { if (i > 0 && a[i] <= a[i - 1]) cur = 0; cur++; res = Math.max(res, cur); } 

Answer 2

目前尚不清楚相同的元素是否被认为是有序的。 如果没有足够的元素来创建更大的maxLength，也可以return 。

 public static int maxLength(int[] array) { if (array.length <= 1) return array.length; // check for null also int maxLength = 1; int curLength = 1; for (int i = 1; i < array.length; i++) { //extra check to finish earlier if possible (you may omit it) if ((array.length - i + curLength) <= maxLength) return maxLength; if (array[i] > array[i-1]) //use >= if equal elements count too curLength++; else { if (maxLength < curLength) maxLength = curLength; curLength = 1; } } //final check (in case the last element is included in maxLength) if (maxLength < curLength) return curLength; return maxLength; }