louisfghbvc的部落格

思路:

演算法LDS，跟LIS完全一樣，只不過記得要記錄從誰而來，然後注意單調的意思，不是絕對遞減，而是單調，所以比如:888 那最大單調遞減為 888，之前題目沒看清楚，卡許久。

先介紹 LDS 演算法，舉例89321

那解法則為，先開一維陣列lds[5]，這個陣列代表的意思為從第0個數字到第i個數字的當前最大lds多長。如lds[2]，就是指從0~2 最大lds為多長，一開始先令所有lds[0]~lds[4] 為1代表他們目前最長都只有1

公式為 lds[j] = max(lds[i] + 1, lds[j])。甚麼意思呢?

意思是 for(int i = 0; i < 5; ++i){

                               for(int j = i +1; j < 5; ++j){

                      if(arr[i] >= arr[j]) //(單調關係 有等號), 代表i後面可以接續j

                         lds[j] = max(lds[i] + 1, lds[j]);  => j的lds長度 不是自己，就是從第i個的lds + 1

                }

           }

運算為結果為lds[0] = 1, lds[1] = 1, lds[2] = 2, ..... lds[4] = 4。 最長為9321、8321。

如果看懂上面的程式碼怎麼運作的話。那接下來再延伸紀錄從誰而來，注意題目是問最大單調，所以如果有兩個lds長度一樣的話，如何判斷誰比較大呢，那就是那兩個看前一個數值誰大了，紀錄較大數值。而比較晚出現的數值，不是會延長lds，不然就是會比原本數值lds前一個數值還要大(公山小) 。直接上代碼。從代碼理解吧。

代碼:

#include <iostream>
#include <cstring>
using namespace std;
string str;
int lds[55], preve[55];
void trace(int i){
    if(preve[i] != -1){
        trace(preve[i]);
    }
    cout << str[i];
}
int main()
{

    while(cin >> str){
        for(int i = 0; i < str.length(); ++i){
            lds[i] = 1;
            preve[i] = -1;
        }
        int mx = 0, pos = 0;
        for(int i = 0; i < str.length(); ++i){
            for(int j = i + 1; j < str.length(); ++j){
                if(str[i] >= str[j]){
                    if(lds[i] + 1 >= lds[j]){ // lds[j] 有可能會跟lds[i] + 1一樣 這時前一個數值就能直接被換掉
                        lds[j] = lds[i] + 1;
                        preve[j] = i; // 直接換掉之前數值，因為越晚出現的一定會更大(想一想)
                    }
                }
            }
            if(lds[i] >= mx){ // 紀錄 最長lds長度，以及是哪個位置為最長， 一樣的話越後面出現會越大(比如123，結果為3)
                mx = lds[i];
                pos = i;
            }
        }
        trace(pos);
        cout << "\n";
    }
    return 0;
}
/*
5687643821
456879421
89321
11234
*/