[数据结构与算法]动态规划小题——最长递增子序列

? ? ? 给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A{5， 6， 7， 1， 2， 8}，则其最长的单调递增子序列为{5，6，7，8}，长度为4.

这边给出动态规划DP数组 的算法：首先将问题转换，dp[i]表示以A[i]结尾的最长递增子序列（注意：这边与最长公共子串不一样，子序列可以是夹断的序列）根据数学归纳思想一般到特殊：可以先假设i之前的子序列长度已知，那么如何求dp[i]？

动态转移方程为：

?！！可以想象为当前的dp值为之前<A[i]的数据的dp数组的最大值+1

代码实现：

int data[] = {10,9,2,5,3,7,101,18};
  int dp[] = {1,1,1,1,1,1,1,1};
  
  for(int i = 0;i < 8;i ++)
  {
  	for(int j = 0;j < i;j ++)
  	{
  		if(data[i]>data[j])
  		{
  			dp[i] = max(dp[i],dp[j]+1);
		  }
	  }
  }

dp的初始化为1，即本身A[i]可为一个子序列