题目： 给定数组arr,返回arr的最长递增子序列 举例 arr=[2,1,5,3,6,4,8,9,7],返回的最长递增子序列为[1,3,4,8,9]
解答：
1.生成长度为N的数组dp,dp[i]表示在以arr[i]这个结尾的情况下，arr[0...i]中的最大递增子序列长度。 2.对第一个数arr[0]来说，令dp[0]=1,接下来从左到右依次算出每个位置的数结尾的情况下，最长递增子序列长度。 3.假设计算到位置i,求以arr[i]结尾情况下的最长递增子序列长度，dp[i]。 dp[i]=max{dp[j]+1(0<=j<i,arr[j]<arr[i])}。如果arr[0...i-1]中所有的数都不比arr[i]小，令dp[i]=1. int max1(int curMaxdp, int curdp) { return curMaxdp > curdp ? curMaxdp : curdp; } for (int i = 0; i < strlen(arr); i++) { dp[i] = 1; for (int j = i-1; j >= 0; j--) { if(arr[j] <= arr[i]) dp[i] = max1(dp[i], dp[j] + 1); } }求出例题中的dp=[1,1,2,2,3,3,4,5,4]
1.然后dp数组，找出最大值以及位置。 2.向左遍历，在遍历的过程中，如果满足dp[i]=dp[i+1]-1,arr[i]
#include <stdio.h> #include <iostream> using namespace std; int max1(int curMaxdp, int curdp) { return curMaxdp > curdp ? curMaxdp : curdp; } int getdp(int arr[]) { int dp[9]; for (int i = 0; i < 9; i++) { dp[i] = 1; for (int j = i-1; j >= 0; j--) { if(arr[j] <= arr[i]) dp[i] = max1(dp[i], dp[j] + 1); // cout<<dp[i]<<" "; } } int len; int value = 0; for (int index = 1; index < 9; index++) { if( dp[index] > dp[value]) value = index; len = dp[value]; } int lis[100]; lis[--len] = arr[value]; //cout<<arr[value]<<" "; for (int i = value ; i>=0; i--) { if (arr[i] < arr[value] && dp[value] == dp[i] + 1 ) { lis[--len] = arr[i]; value = i; } } for(int i=0;i<5;i++) cout<<lis[i]<<" "; return dp[value]; } int main () { int arr[]={2,1,5,3,6,4,8,9,7}; //int dp[9]; int num; num = getdp(arr); //cout<<num; return 0; }