6、求数组中最长递增子序列

短命女 2022-05-27 10:15 170阅读 0赞

写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中最长递增子序列的长度。  
例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长递增子序列为1，2，4，6。

import java.util.Arrays;
    import java.util.Random;
    
    public class LISUpdate {
    
        public static void main(String[] args){
    
            System.out.println("Generating a random array...");
            LISUpdate lisUpdate=new LISUpdate();
            int[] oldArray=new int[10];
            oldArray=lisUpdate.randomArray();
            System.out.println(Arrays.toString(oldArray)); //输出生成的随机数组
            System.out.println("each LIS array:"); //输出每次计算时arrayOut数组的内容，便于观察
            System.out.println("LIS length nlogn is:"+lisUpdate.getLength(oldArray)); //输出最长递增子序列的长度
        }
    
        public int[] randomArray(){ //生成一个10以内的数组，长度为10
            Random random=new Random();
            int[] randomArray=new int[10];
            for (int i = 0; i < 10; i++) {
                randomArray[i]=random.nextInt(10);
            }
    
            return randomArray;
        }
    
        public int BinarySearchPosition(int arrayOut[],int left,int right,int key){ //二分查找要替换的位置
    
            int mid;
    
            if (arrayOut[right]<key) {
                return right+1;
            }else {
                while(left<right){
                    mid=(left+right)/2;
                    if (arrayOut[mid]<key) {
                        left=mid+1;
                    }else {
                        right=mid;
                    }       
                }
                    return left;
            }
    
        }
    
        public int getLength(int[] arrayIn){ //获取最长递增子序列的长度
    
            int position;
            int len=1;
    
            int[] arrayOut=new int[arrayIn.length+1];//arrayOut[0]没有存放数据
            arrayOut[1]=arrayIn[0]; //初始化，长度为1的LIS末尾为arrayIn[0]
            for (int i = 1; i < arrayIn.length; i++) {
                position=BinarySearchPosition(arrayOut, 1, len, arrayIn[i]);
                arrayOut[position]=arrayIn[i];
                System.out.println(Arrays.toString(arrayOut));
                if (len<position) {
                    len=position;
                }
            }
    
            return len;
        }
    
    }

对于求最长递减子序列，则可以直接将原数组进行“反转”操作，然后求出反转之后的数组的最长递增子序列的长度即为最长递减子序列的长度。

> 思路：对前i个元素的任何一个递增子序列，如果这个子序列的最大元素比array\[i+1\]小，则将array\[i+1\]添加到该子序列尾部，构成一个新的递增子序列。 否则取一半的下标mid，mid时当前right+left/2，判断arrayOut\[mid\]

Generating a random array...
    [0, 8, 2, 6, 9, 1, 2, 1, 6, 8]
    each LIS array:
    2
    [0, 0, 8, 0, 0, 0, 0, 0, 0, 0, 0]
    2
    [0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
    3
    [0, 0, 2, 6, 0, 0, 0, 0, 0, 0, 0]
    4
    [0, 0, 2, 6, 9, 0, 0, 0, 0, 0, 0]
    2
    [0, 0, 1, 6, 9, 0, 0, 0, 0, 0, 0]
    3
    [0, 0, 1, 2, 9, 0, 0, 0, 0, 0, 0]
    2
    [0, 0, 1, 2, 9, 0, 0, 0, 0, 0, 0]
    4
    [0, 0, 1, 2, 6, 0, 0, 0, 0, 0, 0]
    5
    [0, 0, 1, 2, 6, 8, 0, 0, 0, 0, 0]
    LIS length nlogn is:5

时间复杂度为O(N\*log2N)

注：

> 1、上面代码中输出的arrayOut数组并不是最长递增子序列,只反映了最长子序列，因为上面的解释已经说明了，顺序发生了变化。  
> 2、也不是最快求解，见下面

\[8, 8, 4, 1, 8, 9, 4, 5, 1, 2\]  
有3组解：  
4、8、9  
1、8、9  
1、4、5  
按照程序跑下来，应该是 1、2、5  
最后的 2和 4 发生了替换。

参考：[https://blog.csdn.net/iniegang/article/details/47681191][https_blog.csdn.net_iniegang_article_details_47681191]

[https_blog.csdn.net_iniegang_article_details_47681191]: https://blog.csdn.net/iniegang/article/details/47681191