动态规划3.3 最长递增子序列

 问题：

　　在一个数组中寻找最长递增子序列。

动态规划方法：

　　当一个数要加入进来的时候有两种方法：

　　1、前面的数都比当前的数大（或者相等），因此，以这个数为止的最长递增子序列长度就是1。数组中的第一个数一般预先填好，或者设置哨兵。

　　2、前面的数有比当前的数小的，那么以这个数为止的最长递增子序列长度就是states[i] = max(states[i], states[j] + 1)；所以对于每一个states[i]要

　　　  遍历它前面的states数组，并且对于每一个num[i] 要比较它前面的num数组来作为控制条件。

代码：

#include <iostream>
#include <algorithm>

int main()
{
    #define LEN 7
    int num[ LEN ] = {2, 9, 3, 6, 5, 1, 7};
    
    int states[LEN] = {0};
    
    states[0] = 1;
    
    int max_subsequence = 1;
    for(int i = 1; i < LEN; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(num[i] > num[j])
            {
                states[i] = std::max(states[i], states[j] + 1);
            }
        }
        max_subsequence = std::max(max_subsequence, states[i]);
    }
    
        
    std::cout << "max_subsequence : " << max_subsequence << std::endl;
    
    return 0;
}

运行结果：

 

 把最长子序列之一打印出来，需要借助一个pre数组，代码：

#include <iostream>
#include <algorithm>
#include <stack>
int main()
{
    #define LEN 7
    int num[ LEN ] = {2, 9, 3, 6, 5, 1, 7};
    int pre[ LEN ] = {0};  // 用于记录前一个数的索引
    pre[0] = -1;
    
    int states[LEN] = {0};
    states[0] = 1;
    
    for(int i = 1; i < LEN; i++)   // 这个for循环里面先不记录递增序列的全局最大值，最后统一搜索
    {
        pre[i] = -1;
        for(int j = 0; j < i; j++)
        {
            if(num[i] > num[j])
            {
                if(states[j] + 1 > states[i])
                {
                    states[i] = states[j] + 1;
                    pre[i] = j;
                }
            }
        }
    }
    
    int max_subsequence = 1;
    int max_index = 0;
    for(int i = 0; i < LEN; i++)    // 统一搜索最大值
    {
        if(states[i] > max_subsequence)
        {
            max_subsequence = states[i];
            max_index = i;
        }
    }
        
    std::stack<int> s;
    while(max_index != -1)
    {
        s.push(num[max_index]);
        max_index = pre[max_index];
    }
    
    std::cout << "max_subsequence : " << max_subsequence << std::endl;
    
    std::cout << "subsequence : ";
    while(!s.empty())
    {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;
    
    return 0;
}

运行结果：