亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

單調(diào)減子序列（java實現(xiàn)）

Keagan / 1597人閱讀

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

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

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

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

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

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

其他情況不做處理

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

比如輸入：
6
2 1 2 1 2 1
輸出應(yīng)為 2 1

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

代碼：

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]結(jié)尾的 子序列中 值不同但長度都是最長得單調(diào)減小的子序列的數(shù)量
            if(dp[i] > 1){//如果  不是只有一個數(shù)字的時候
                Set sl = new HashSet<>();
                for(int j = i - 1; j >= 0; --j){
                    //從右向左查詢  只查詢第一次遇到的并且是最大長度的 size[i]
                    // 沒有記錄路徑 通過 arr[j] > arr[i] && dp[j] == dp[i] - 1 來確定是否是前一個轉(zhuǎn)移
                    // 遇到相同結(jié)尾的情況，更右邊的已經(jīng)包含了左邊的情況
                    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{
                //只有一個數(shù)字是 數(shù)量為1
                size[i] = new BigInteger("1");
            }
        }
        BigInteger maxBigI = new BigInteger("0");
        Set set = new HashSet<>();
        //遍歷整個序列  找出最大長度 且值不同的序列的數(shù)量
        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());
    }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/69324.html

相關(guān)文章

  • Java String、StringBuffer和StringBuilder類

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

    Jason 評論0 收藏0

  • Java與Python詳細對比

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

    tianhang 評論0 收藏0

  • Java與Python詳細對比

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

    sydMobile 評論0 收藏0

  • Java知識點總結(jié)（常用類-字符類）

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

    xiaokai 評論0 收藏0

  • 賬戶變動合并提交方案

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

    MoAir 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<