经典算法——最长平台问题

经典最长平台算法

已知一个已经从小到大排序的数组，这个数组中的一个平台（Plateau）就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在1，2，2，3，3，3，4，5，5，6中［1］、［2，2］、［3，3，3］、［4］、［5，5］、［6］都是平台。尝试编写一个程序，接受一个数组，把这个数组中最长的平台找出来。在上面的例子中3，3，3就是该数组中最长的平台。

要求：
1、使用的变量越少越好。
2、把数组的元素每一个都只查一次就得到结果。
3、程序的语句也要越少约好。

我尝试写了这个问题的解法，程序还有待优化（还有新的想法，先给出比较直观的解法）

import java.lang.*;

public class LargestPlateau{

        public static void getLargestPlateau(int[] numberSequence){
                int cnt=1;
                int index=0;
                int largestTimes=1;
                int times=1;

                while(cnt<numberSequence.length){
                        if(numberSequence[cnt-1]!=numberSequence[cnt]){
                                if(largestTimes<times){
                                        largestTimes=times;
                                        index=cnt-times;
                                        times=1;
                                }else{
                                        times=1;
                                }

                        }else{
                                ++times;
                        }
                        ++cnt;
                }

                for(int i=index;i<index+largestTimes;++i){
                        System.out.print(numberSequence[i]+" ");
                }

                System.out.println();
        }

        public static void main(String[] args){
                int[] numberSequence={1,2,2,3,3,3,4,5,5,5,5,5,6};
                LargestPlateau.getLargestPlateau(numberSequence);
        }
}

如果只是需要计算出一串元素的最长平台的长度，那么还可以有以下的解法（参考David Gries编写的相关专著）：

import java.lang.*;

public class LargestPlateau1{
        public static int getMaxLengthofLargestPlateau(int[] numberSequence){
                int size=numberSequence.length;
                int length=1;

                for(int i=1;i<size;++i){
                        if(numberSequence[i]==numberSequence[i-length]){
                                length++;
                        }
                }

                return length;          //the length of largest plateau
        }

        public static void main(String[] args){
                int[] numberSequence={1,2,2,3,3,3,4,5,5,5,5,5,6,6};
                System.out.println("The length of largest plateau : "+LargestPlateau1.getMaxLengthofLargestPlateau(numberSequence));

        }
}