上升子序列

上升子序列系列

• 求最大的上升子序列的和
• • 例子
  • 解题思路
  • 代码
• 求最长的上升子序列的长度
• • 例子
  • 解题思路
  • 代码

求最大的上升子序列的和

      一个只包含非负整数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。

对于给定的一个序列{a1, a2, …,aN}，我们可以得到一些上升的子序列{ai1, ai2, …, aiK}，这里1 ≤ i1 < i2 <…< iK ≤ N。

例如：对于序列{1, 7, 3, 5, 9, 4, 8}，有它的一些上升子序列，如{1, 7}, {3, 4, 8}等等。

这些子序列中序列和最大的是子序列{1, 3, 5, 9}，它的所有元素的和为18。

对于给定的一个序列，求出它的最大的上升子序列的和。

注意：最长的上升子序列的和不一定是最大的哦。

例子

输入

7
1 7 3 5 9 4 8

输出

18

解题思路

动态规划：当前解可由上一个阶段的解推出，因此，我们可以把问题化成一个更小的子问题。

a[]={1 7 3 5 9 4 8}
b[]数组用来存放每个上升子序列的和。

初始化为a[]
第1个数：b[0]=1
第2个数：i=1，j=0 a[0] 第3个数：i=2，j=0 a[0] 第4个数：i=3，j=0 a[0] i=3，j=2 a[2] 第5个数：i=4，j=0 a[0] i=4，j=2 a[2] i=4，j=3 a[3] 第6个数：i=5，j=0 a[0] i=5，j=2 a[2] 第7个数：i=6，j=0 a[0] i=6，j=1 a[1] i=6，j=2 a[2] i=6，j=3 a[3] i=6，j=5 a[5] 代码

#include
using namespace std;
const int N=1e3+5;
int a[N],b[N];

int main()
{
    int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[i]=a[i];
	} 
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(a[j]<a[i]){
				b[i]=max(b[i],b[j]+a[i]);
			}
		}
	}
	int max=0;
	for(int i=0;i<n;i++){
		if(b[i]>max){
			max=b[i];
		}
	}
	cout<<max;
    return 0;
}

求最长的上升子序列的长度

      一个只包含非负整数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。

对于给定的一个序列{a1, a2, …,aN}，我们可以得到一些上升的子序列{ai1, ai2, …, aiK}，这里1 ≤ i1 < i2 <…< iK ≤ N。

例如：对于序列{1, 7, 3, 5, 9, 4, 8}，有它的一些上升子序列，如{1, 7}, {3, 4, 8}等等。

这些子序列中序列和最大的是子序列{1, 3, 5, 9}。

对于给定的一个序列，求出它的最长的上升子序列的长度。

例子

输入

9
2 7 1 5 6 4 3 8 9

输出

5

解题思路

我们定义d[i]来表示前i个数以a[i]结尾的最长上升子序列的长度。

初始化都是1。

a[]={2 7 1 5 6 4 3 8 9}
第1个数：d[0]=1，子序列：{2}
第2个数：i=1，j=0 a[0] 第3个数：d[2]=1，子序列：{1}
第4个数：i=3，j=0 a[0] …
以此类推，换汤不换药

代码

#include
using namespace std;
const int N=1e3+5;
int a[N],b[N],d[N];

int main()
{
    int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		d[i]=1;
	} 
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			if(a[j]<a[i]){
//				b[i]=max(b[i],b[j]+a[i]);
				d[i]=max(d[i],d[j]+1);
			}
		}
	}
	int max=0;
	for(int i=0;i<n;i++){
		if(d[i]>max){
			max=d[i];
		}
	}
	cout<<max;
    return 0;
}