题解 | #最长上升子序列(一)#
最长上升子序列(一)
http://www.nowcoder.com/practice/5f65ccbb025240bd8458eb6479c2612e
这是一道动态规划题目。将其分解为子问题，即分解成求解n个 以0到n-1下标的数为结尾的子序列的最大长度的问题。
可以用一个dp数组保存每个数做结尾时对应的最大长度。
假设一个以第i个元素arr[i]结尾的子序列Si，那么Si的长度是由i在Si中的前一个元素arr[j]决定的，Si的长度就等于Sj的长度加一。
这前面一个数arr[j]必须要满足两个条件：
- arr[j]<arr[i],这样才能构成严格上升
- dp[j]的值在i之前的所有dp中最大，这样我们求的才是最大长度。
using namespace std;
int main(){
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
vector<int> dp(n,1);//以i下标的数为结尾的子序列的长度
for(int i=1;i<n;i++){
int mx=0;
for(int j=0;j<i;j++){
//每一个元素的dp值==在它之前的，比它小的元素中最大的dp值加一
if(arr[i]>arr[j])
mx=max(mx,dp[j]);
}
dp[i]=mx+1;
}
int res=1;
for(int i=0;i<n;i++)
res=max(res,dp[i]);
cout<<res;
return 0;
}
时间复杂度：O(n^2),空间复杂度：O(n)