最長遞增子序列問題【C++】-創(chuàng)新互聯(lián)

**問題：**最長遞增子序列問題主要分為了兩類，即最長連續(xù)遞增子序列的求解，以及最長遞增子序列的求解（不一定要連續(xù)）。求解過程總結(jié)如下：
算法標(biāo)簽：動態(tài)規(guī)劃、深度優(yōu)先搜索、二分查找
代碼：01_dp求解最長連續(xù)遞增子序列長度

成都創(chuàng)新互聯(lián)公司堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的鞏留網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

#include#include
using namespace std;
const int maxN = 1e5+9;
int dp[maxN];   // dp[i]表示以第i個元素作為最后元素的最長連續(xù)遞增子序列的的長度
int res = -1;
int main(){int n;
    int arr[maxN];
    cin >>n;
    for( int i=1; i<=n; i++ ){cin >>arr[i];
    }
    dp[1] = 1;
    for( int i=2; i<=n; i++ ){if(arr[i] >arr[i-1]){dp[i] = dp[i-1] + 1;
        }else{dp[i] = 1;
        }
        res = max(res, dp[i]);
    }
    cout<< res;
    return 0;
}

代碼：02_dp求最長遞增子序列長度(n*n)

#include#include
using namespace std;
const int maxN = 1e5+9;
int dp[maxN];   // dp[i]表示以第i個元素作為最后元素的最長遞增子序列的長度
int res = 1;
int main(){int n;
    int arr[maxN];
    cin >>n;
    for( int i=1; i<=n; i++ ){cin >>arr[i];
    }
    for( int i=1; i<=n; i++ ){dp[i] = 1;
        for( int j=1; j<=i-1; j++ ){if(arr[i] >arr[j]){dp[i] = max(dp[i], dp[j]+1);
            }
        }
        res = max(res, dp[i]);
    }
    cout<< res;
    return 0;
}

代碼：03_dp求最長遞增子序列長度(n*logn)

#includeusing namespace std;

const int maxN = 1e5 + 9;
int n, res;
int dp[maxN];   // 存儲當(dāng)前偽最長上升子序列[與真實(shí)最長上升子序列的長度相同]
int main(){int arr[maxN];
    cin >>n;
    for( int i=1; i<=n; i++ ){cin >>arr[i];
    }
    dp[1] = arr[1];
    res = 1;
    for( int i=2; i<=n; i++ ){if(arr[i] >dp[res]){dp[++res] = arr[i];
        }else{int tmp = lower_bound(dp+1, dp+res+1, arr[i]) - dp;
            dp[tmp] = arr[i];
        }
    }
    cout<< res;
    return 0;
}

代碼：04_dfs求解最長遞增子序列

#include#include#include
using namespace std;
int dp[100009];
int res = 0;
string ans;
void dfs(int currentIndex, int previousIndex, string tmp, string str){if(currentIndex == str.length()){if(res< tmp.length()){ans = tmp;
            res = tmp.length();
        }
        return;
    }

    if(currentIndex == 0 || str[currentIndex] >str[previousIndex]){dfs(currentIndex+1, currentIndex, tmp+str[currentIndex], str);
        dfs(currentIndex+1, previousIndex, tmp, str);
    }else{dfs(currentIndex+1, previousIndex, tmp, str);
        dfs(currentIndex+1, previousIndex, ""+str[currentIndex], str);
    }
}
int main(){string str;
    cin >>str;
    dfs(0, -1, "", str);
    cout<< ans;
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：最長遞增子序列問題【C++】-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://muchs.cn/article4/csgpie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供軟件開發(fā)、網(wǎng)站策劃、網(wǎng)站營銷、域名注冊、做網(wǎng)站、網(wǎng)站設(shè)計

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容