动态规划(c++)

很经典

开辟一个和给定数组大小相等的数组long_list[n]，记录每个位置为最终数字的最大子序列（相当于是每个位置的最大子序列）
在遍历时，每次向后遍历数据回溯之前的数据，加上（前面数据中 小于当前位置数据且 最大子序列 最大 的数据的最大子序列数）。

#include<iostream>
#include<vector>
#define INT_MIN     (-2147483647 - 1)
#define INT_MAX       2147483647
using namespace std;
//6 3 1 5 2 3 7
int longest(int* lists, int num) {
    int temp;
    int last_min = lists[0];
    int max_num = INT_MIN;
    int* long_list = new int[num];
    for (int i = 0; i < num; i++) long_list[i] = 1;
    for (int i = 1; i < num; i++) {
        temp = 0;
        //回溯之前的数据 
        for (int j = 0; j < i; j++) {
        	//小于当前数据的数字
            if (lists[j] < lists[i])
            {
            	//记录子序列数最大的
                temp = max(long_list[j],temp);
            }
        }
        //相加
        long_list[i] = temp + long_list[i];
        //记录最大子序列数
        max_num = max (max_num,long_list[i]);
        
    }
    return max_num;
}

int main() {
    int num;
    int* lists;
    cin >> num;
    lists = new int[num];
    for (int i = 0; i < num; i++) {
        cin >> lists[i];
    }
    cout << longest(lists, num) << endl;
    return 0;
}