429-动态规划算法-最长非降子序列LIS

谁借莪１个温暖的怀抱￠ 2022-09-05 04:29 143阅读 0赞

## LIS问题：求序列的最长非降（升序）子序列的长度 ##

**5 3 4 1 8 7 9**  
我们看上面这个序列。  
**显然，5和3不能构成非降子序列。3和4就可以构成非降子序列。以此类推。**  
**最长的非降子序列是3479**

**朴素解法：不一定得到最优解，无效的解法 但是要求算法时间复杂度：O(n^2)**

## 动态规划算法解决 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        
    	int ar[] = {
         5, 3, 4, 1, 8, 6, 7, 10 };
    	const int n = sizeof(ar) / sizeof(ar[0]);
    	int dp[n] = {
         0 };
    	int maxval = 0;//初始化最大值
    
    	for (int i = 0; i < n; ++i)
    	{
          //O(n)
    		dp[i] = 1;//因为每个元素可以自己构成一个非降子序列
    		for (int j = 0; j < i; ++j)
    		{
          //O(n)
    			if (ar[j] <= ar[i] && 1 + dp[j] > dp[i])
    			{
        
    				dp[i] = 1 + dp[j];
    			}
    		}
    
    		if (dp[i] > maxval)
    		{
        
    			maxval = dp[i];
    		}
    	}
    
    	cout << maxval << endl;//5
    
    	return 0;
    }

**运行截图如下**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e501ffd7884e45f1b897d4e86bc1ccab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/02a1f003c43f4f97982064d14acc22ba.png