Algorithm 01 : 寻找最长有序子序列

Question : To find max sorted contiguous subsequence of an Array.

问题：查找数组中的最长有序子序列。

/**
  * @author YuHuang
  * @vision 2011-10-03
  * This program is only for algorithm training.
  *
  */


public class MaxSortedContiguousSubsequence {

        private int[] rArray;

        public void doSearch(int[] sArray){
                int len = sArray.length;
                int[] markArray=new int[len];

                markArray[len-1]=0;
                for(int index=len-2;index>=0;--index){
                        if(sArray[index]<=sArray[index+1]){
                                markArray[index]=markArray[index+1]+1;
                        }
                }

                int startIndex=0;
                for(int index=1;index<=len-1;++index){
                        if(markArray[index]>markArray[startIndex]){
                                startIndex=index;
                        }
                }

                rArray=new int[markArray[startIndex]];
                for(int index=startIndex;index<startIndex+markArray[startIndex];++index){
                        rArray[index-startIndex]=sArray[index];
                }

        }

        public void printResult() {
                System.out.print("Max Sorted Contiguous Subsequence : ");
                for(int elem : rArray){
                        System.out.print(elem+" ");
                }
        }

        public static void main(String[] args){
                int[] sArray={2,3,1,2,3,4,5,2,1,3};
                MaxSortedContiguousSubsequence mscs = new MaxSortedContiguousSubsequence();
                mscs.doSearch(sArray);
                mscs.printResult();
                System.out.println();
        }
}

如果有更低复杂度的算法，请告知，谢谢！