單調減子序列（java實現）

Keagan 發布于2019-08-15 15:55 / 1515人閱讀

摘要：給定整數序列的長度和整數序列中依次的值，請你求出這個整數序列中最長的單調減小的子序列的長度以及不同但長度都是最長得單調減小的子序列的數量。輸入第行為一個整數，表示輸入的整數序列的長度。對于問題，聲明以第個元素為結尾的子序列的最長的長度。

題目：從一個由N個整數排列組成的整數序列中，自左向右不連續的選出一組整數，可以組成一個單調減小的子序列（如從{68 69 54 64 68 64 70 67 78 62 98 87}中我們可以選取出{69 68 64 62}這個子序列；當然，這里還有很多其他符合條件的子序列）。給定整數序列的長度和整數序列中依次的值，請你求出這個整數序列中“最長的單調減小的子序列的長度”以及“不同但長度都是最長得單調減小的子序列的數量”。

   輸入第1行為一個整數N，表示輸入的整數序列的長度（1≤N≤50000）。輸入第2行包括由空格分隔的N個整數（每個整數都在32位長整型范圍內）。

輸出包括一行，為兩個數字，分別為針對給定的整數序列求出的“最長的單調減小的子序列的長度”以及“值不同但長度都是最長得單調減小的子序列的數量”
樣例輸入
12
68 69 54 64 68 64 70 67 78 62 98 87
樣例輸出
4 2

對于這個題，一共有兩個小部分的問題要解決。前一個問題是最長不上升子序列，屬于LIS問題，使用動態規劃解決，后一個問題屬于去重問題。
對于LIS問題，聲明dp[i] 以第i個元素為結尾的子序列的最長的長度。
對第i個元素，與前i-1個元素進行比較：
dp[i] = 1; //當末尾只要一個元素時長度為1
如果 arr[i] < arr[j]:

如果dp[i] < dp[j] + 1
此時dp[i]的值會被更新為dp[j] + 1

其他情況不做處理

對于去重問題：
“值不同但長度都是最長得單調減小的子序列的數量” 這里說的是：

比如輸入：
6
2 1 2 1 2 1
輸出應為 2 1

2 1 2 1 這兩個是值相同的，所以應該當做一個
使用size[i] 數組去記錄第i元素為結尾時，值不同但長度都是最長得單調減小的子序列的數量
每次在dp更新一遍以后，進行size的更新。
去掉相同值的情況，如果只去關注最后結尾時：
因為每次遍歷都會更新狀態，也就是說如果有相同值的時候后者會把前者的情況都會過一遍，所以只要每次更新時保證只取相同值的最后一個出現的元素位置的size[j]即可，也就是最右邊的那個。
對于i元素所構成的最長子序列的前一個元素可能有很多不同值，所以要記錄這些值,并只取最右邊的。
最后size 和 dp都已經生成了最終數組
然后對整個數組進行遍歷，找出最大序列且值不同的序列的數量
方法同找單個i位置元素的值不同但長度都是最長得單調減小的子序列的數量一致
其他說明：
數據較大使用java中的BigInteger
遍歷找值不同但長度都是最長得單調減小的子序列的數量時使用倒序查找

代碼：

Scanner read = new Scanner(System.in);
        int n = read.nextInt();
        long[] arr = new long[n];
        long[] dp = new long[n];
        BigInteger[] size = new BigInteger[n];
        for(int i = 0; i < n; ++i){
            arr[i] = read.nextLong();
        }
        long max = 0;
        
        for(int i = 0; i < n; ++i){
            dp[i] = 1;
            size[i] = new BigInteger("0");
            for(int j = 0; j < i; ++j){
                if(arr[j] > arr[i]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                    }
                }
            }
            if(dp[i] > max){
                //更新 最長長度
                max = dp[i];
            }
            // 確定以arr[i]結尾的 子序列中 值不同但長度都是最長得單調減小的子序列的數量
            if(dp[i] > 1){//如果  不是只有一個數字的時候
                Set sl = new HashSet<>();
                for(int j = i - 1; j >= 0; --j){
                    //從右向左查詢  只查詢第一次遇到的并且是最大長度的 size[i]
                    // 沒有記錄路徑 通過 arr[j] > arr[i] && dp[j] == dp[i] - 1 來確定是否是前一個轉移
                    // 遇到相同結尾的情況，更右邊的已經包含了左邊的情況
                    if(arr[j] > arr[i] && dp[j] == dp[i] - 1 && !sl.contains(arr[j])){
                        sl.add(arr[j]);//去重
                        size[i] = size[i].add(size[j]);
                    }
                }
            }else{
                //只有一個數字是 數量為1
                size[i] = new BigInteger("1");
            }
        }
        BigInteger maxBigI = new BigInteger("0");
        Set set = new HashSet<>();
        //遍歷整個序列  找出最大長度 且值不同的序列的數量
        for(int i = n - 1; i >= 0; --i){
            if(dp[i] == max && !set.contains(arr[i])){
                set.add(arr[i]);
                maxBigI = maxBigI.add(size[i]);
            }
        }
        System.out.println(max + " " + maxBigI.toString());
    }

云服務器 GPU云服務器最大子序列最長遞增子序列最長公共子序列單序列號

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69324.html

Java String、StringBuffer和StringBuilder類

摘要：可以調用方法將其轉換為一個對象是線程安全的，則沒有實現線程安全功能，所以性能略高。通過串聯更方便將該對象與的對象進行比較。追加字符串插入替換刪除反轉輸出輸出改變的長度，將只保留前面部分 String類是不可變類，即一旦一個String對象被創建以后，包括在這個對象中的字符序列是不可改變的，直至這個對象被銷毀 StringBuffer對象則代表一個字符序列可變的字符串，當一個String...

Jason 2019-08-14 16:58 評論0 收藏0
Java與Python詳細對比

摘要：序列化的這種過程，我們將其稱為腌制。而把模塊編譯成二進制語言程序的這個過程叫做字節編譯，這個過程會產生一個與編譯的模塊對應的文件。常量：在Python中常量的使用并不像java等其他編程語言一樣有特定的常量實現的關鍵字，在Python中定義需要用對象的方法來創建。 showImg(https://segmentfault.com/img/bVP6mZ?w=1232&h=703); ...

tianhang 2019-07-25 12:03 評論0 收藏0
Java與Python詳細對比

摘要：序列化的這種過程，我們將其稱為腌制。而把模塊編譯成二進制語言程序的這個過程叫做字節編譯，這個過程會產生一個與編譯的模塊對應的文件。常量：在Python中常量的使用并不像java等其他編程語言一樣有特定的常量實現的關鍵字，在Python中定義需要用對象的方法來創建。 showImg(https://segmentfault.com/img/bVP6mZ?w=1232&h=703); ...

sydMobile 2019-08-16 12:07 評論0 收藏0
Java知識點總結（常用類-字符類）

摘要：知識點總結常用類字符類知識點總結常用類類型用來比奧斯在編碼中的字符。使用給定中的字符替換此序列的子字符串中的字符。將此字符序列用其反轉形式取代。返回最右邊出現的指定子字符串在此字符串中的索引。 Java知識點總結（常用類-字符類） @(Java知識點總結)[Java, Java常用類] [toc] Char char類型用來比奧斯在Unicode編碼中的字符。Unicode用來處理各...

xiaokai 2019-08-15 15:34 評論0 收藏0
賬戶變動合并提交方案

摘要：起因及介紹在早期的賬戶系統中，但凡有賬戶變動，就會執行一次數據庫操作。這時，在一次處理過程中，合并同一個賬戶的所有操作，最后只提交一次，就能帶來很大的優化空間。根據業務需要，進行增減轉賬凍結解凍操作。起因及介紹在早期的賬戶系統中，但凡有賬戶變動，就會執行一次數據庫操作。這樣在有復雜一些業務操作的時候，例如單筆交易涉及多個用戶多個費用的資金劃撥，一個事務內操作數據庫幾十次也就大量的存...

MoAir 2019-08-19 11:15 評論0 收藏0