<p>例如给定一个序列:1,5,2,4,8,3,7,11,17,5,20,11,其中最长递增子序列为:1,2,4,8,11,17,20</p><p>求解思路:可以使用动态规划解决此问题,用两个数组dp[n]和pos[n],其中dp用来表示到第i位时的最长子序列长度,而pos表示在这个最长子序列中上一个元素的位置。这个算法的空间复杂度为O(n),时间复杂度为n的平方。</p><p>第i趟扫描从第i个元素开始,当a[j]>a[i] && dp[j] < dp[i] + 1时更新dp[j] = dp[i] + 1,pos[j] = i,当扫描n趟之后,dp的值为到第i个元素的最长字符串长度是多少,pos的值表示第i个元素最长子序列的上以元素是什么。</p><p>具体代码为:</p>
#include "stdafx.h"
#include <vector>
#include<iostream>
using namespace std;
void max_sub_seq(int a[], int len)
{
int *dp = new int[len];
int *pos = new int[len];
bool flag = false; // 为了输出时进行控制
int i,j;
for (i = 0; i < len; i++)
{
dp[i] = 1;
pos[i] = i;
}
for (i = 0; i < len; i++)
{
for (j = i + 1; j < len; j++)
{
if (a[j] > a[i] && dp[j] < dp[i] + 1)
{
dp[j] = dp[i] + 1; // dp更新
pos[j] = i; //位置更新
}
}
}
pos[0] = -1;
int max = 0;
for (i = 0; i < len; i++)
{
if (dp[i] > dp[max])
max = i;
}
vector<int> result;
for (j = max; j >= 0 && (j == 0 || pos[j] != j);) // 更具pos值向前寻找最长子串的值
{
result.push_back(a[j]);
j = pos[j];
if (flag == true && j == 0)
{
flag = false;
break;
}
}
for (j = result.size() - 1; j >= 0; j--)
cout << result[j] << ' ';
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {1,5,2,4,8,3,7,25,18,9,11,17,5,20,11};
max_sub_seq(a, 15);
return 0;
}
注:代码在VS2013下通过编译,并能正确运行,如有问题请在评论中指出或邮件告知。
版权声明:本文为shouwangcc原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。