最长平台问题描述如下：
一个从小到大排列的数组，这个数组中的一个平台就是连续的一段值相同的元素。例如：122333445中22，333等都是平台，333为最长平台。
一般常见的算法是一个计算机科学家首先给出的。
private static int f1(int[] array) {
if (array == null || array.length == 0)
return 0;
int length = 1;
for (int i = 1; i < array.length; i++) {
if (array[i] == array[i - length])
length++;
}
return length;
}
这段代码的确是简洁优雅的，但是在效率上不是很好。
最长平台有一些特点可以利用，从而使得算法的效率更高。
一个分界点元素指该元素和它的前一个元素不相等。
1 从一个分界点开始剩下的元素个数<=length，则可以直接返回。
2 从一个分界点开始找最大平台，没有必要依次顺序查找，直接跳到该（分界点的坐标+length）的元素进行查找。
如果（分界点的坐标+length）也是一个分界点，则从原来的分界点到新的分界点（分界点的坐标+length）之间的 元素可以丢掉，从新的分界点重新开始查找最长平台。
如果（分界点的坐标+length）不是一个分界点，则它有可能在一个最长平台中，判断之，然后继续。
这里主要是考虑到当前最长平台的长度，算法考虑该长度可以跳过一些元素进行处理。
/**
* 最长平台更快的算法
*/
private static int f2(int[] array) {
if (array == null || array.length == 0)
return 0;
// 下一个要检测的位置,保证array[next]!=array[next-1]。
int next = 1;
for (; next < array.length && array[next] == array[0]; next++)
;
// 第一个平台的长度,next>=1。
int length = next;
while (next < array.length) {
// 如果剩下的元素个数<=length，则不可能有最长平台了
if (array.length - next <= length) {
break;
}
// 向前跳跃length+1,到next+length处进行检查，如果array[next+length]!=array[next+length-1],则
// next - (next+length-1)这段数据可以丢弃.
if (array[next + length] != array[next + length - 1]) {
next = next + length;
} else {
// 这个相等的值所在的平台的值.
int value = array[next + length];
// 这个相等的值所在的平台的最后一个坐标.
int endIndex = next + length + 1;
for (; endIndex < array.length && array[endIndex] == value; endIndex++)
;
endIndex = endIndex - 1;
// 向后跳跃length+1,如果相等，则这个平台是最大平台.
if (array[endIndex - length] == value) {
int startIndex = endIndex - length - 1;
for (; array[startIndex] == value; startIndex--)
;
// 更新最大平台的值
length = endIndex - startIndex;
}
next = endIndex + 1;
}
}
return length;
}
code是比上一个复杂一些，但是速度有了很大的提高，大约提高60%以上。
还有改进的余地，如果在查找一个平台的最后一个坐标或者第一个坐标，可以用2分查找。
分享到：
相关推荐
最长递增序列 算法程序 最长递增序列 算法程序
标题中的“求字符串的最长平台”实际上是指寻找一个数组中具有相同值的连续子序列的最大长度，这在数据结构和算法领域中是一个常见的问题。在C语言编程中，这个问题可以通过遍历数组并比较相邻元素来解决。从给出的...
### 最长公共子序列算法总结 #### 一、O(n^2)算法 在讨论最长公共子序列（Longest Common Subsequence，简称LCS）问题时，通常会提及两种主要的算法实现方式：一种时间复杂度为O(n^2)，另一种则通过优化达到O...
最长公共字串算法，为算法导论上的算法,可以运行，运行时间为O(mn)
如果当前单词更长，更新最长长度，并清空现有的最长单词列表，将新单词添加进去。如果长度相同，但不是已知的最长单词，将其添加到列表中。 4. **处理结果**：遍历完成后，最长单词列表应该包含了所有最长的单词。...
`fasta`算法、`Smith-Waterman`(SW)算法、编辑距离算法以及最长公共子串算法都是这一领域中常用的序列比对方法。下面将详细介绍这些算法。 1. **fasta算法** `fasta`算法是一种快速的全局序列比对方法，由Pearson...
最长模式匹配算法是计算机科学中用于字符串处理的一种重要方法，主要应用于文本编辑器、版本控制系统、数据比较等领域。它的核心目标是在两个字符串中找到最长的相同子串，这对于比较两段字符间的差别尤为关键。在...
最长公共子串的快速搜索算法 最长公共子串的快速搜索算法 最长公共子串的快速搜索算法
用C++实现的最长公共子序列算法，并包含大量的注释，对理解程序很有帮助
最长单调子序列问题是一个经典的计算机科学中的算法问题，主要涉及数据结构和算法设计。在这个问题中，目标是找到一个给定序列中长度最长的单调递增或递减的子序列。这里的“单调”指的是子序列中的元素要么总是递增...
总的来说，动态规划和KR算法都是求解最长公共子序列的有效方法，它们各有特点，适用于不同的编程环境和需求。而KMP算法则专注于高效的字符串匹配，虽然与LCS问题不是直接相关，但在字符串处理领域中同样重要。
实验报告的主题是“算法设计与分析”，关注的是使用动态规划解决最长公共子序列（Longest Common Subsequence, LCS）的问题。动态规划是一种有效的方法，它适用于具有最优子结构和子问题重叠性质的问题。在本实验中...
实现了求最长公共子序列的算法，内容简单易懂，代码也很短
算法实验：计算DAG图最长路径并输出。
最长公共子序列（Longest Common Subsequence，LCS）问题是一个经典的计算机科学问题，主要涉及字符串处理和动态规划算法。在本场景中，我们使用C#编程语言来解决这个问题。C#是一种多范式编程语言，广泛应用于开发...
### 最长公共子序列动态规划算法 在计算机科学领域中，**最长公共子序列问题**（Longest Common Subsequence Problem, LCS）是一个经典的算法问题，它主要应用于文本比较、生物信息学中的DNA序列比对等领域。该问题...
动态规划算法求最长公共子序列 动态规划算法是一种常用的算法思想，它通过将复杂的问题分解成多个小问题，并将这些小问题的解组合起来，来解决复杂的问题。在这里，我们使用动态规划算法来求解最长公共子序列问题。...
算法设计与分析中的一个算法函数，用C编的
这是一个有关算法的压缩包，里面包含二分算法、合并排序、最长公共子序列、最优装载、活动安排算法