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

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

#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];   // 存儲當前偽最長上升子序列[與真實最長上升子序列的長度相同]
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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：最長遞增子序列問題【C++】-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://weahome.cn/article/csgpie.html