最长上升子序列c++运行超时求改进

fanhan123 @ 2024-11-02 20:06:44

#include <bits/stdc++.h>
using namespace std;
const int N=1000;
int a[N],dp[N],t;
int main(){
    cin>>t;
    for (int i=0;i<t;i++){
        cin>>a[i];
        dp[i]=1;
    }
    for (int i=1;i<t;i++){
        int maxv=0;
        for (int j=0;j<i;j++){
            if (a[j]<a[i]){
                dp[i]=max(dp[j]+1,dp[i]);
            }
        }
    }
    int maxs=0;
    for (int i=0;i<t;i++){
        maxs=max(maxs,dp[i]);
    }
    cout<<maxs<<endl;
    return 0;
}

by I_AM_AKer @ 2024-11-02 20:18:53

数组开小了

by EternalRights @ 2024-11-10 10:55:46

lis有规律可循，我们观察题目会发现lis由一串尽可能存在的序列组成，组成规律无非就是小到大。
故而可以结合贪婪算法考虑，设计出来一个较为贪婪的数组去承载lis，结合一维数组即可搭配出花一样的效果：
设计lis数组（上升序列），一次遍历，遍历元素与lis末尾比较，1.大放进去 2.小二分查找lis寻找较大者替换掉。 这样就保证了一个尽可能成立的lis。
贪心+动态规划

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pii = pair<int,int>;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<int>num(n);
    vector<int>lis;
    for ( int i = 0; i < n; i++){
        cin >> num[i];
        if ( lis.empty()){
            lis.push_back(num[i]);
        }
        else{
            if ( num[i] > lis.back()){
                lis.push_back(num[i]);
            }
            else if ( num[i] < lis.back()){
                auto it = lower_bound(lis.begin(),lis.end(),num[i]);
                int j = distance(lis.begin(),it);
                lis[j] = num[i];
            }
        }
    }
    cout << lis.size() << endl;

    return 0;
}