UC知道求助一道算法题
来源：百度知道 编辑：UC知道 时间：2024/06/12 03:41:56
给定一个数组，让你找所有升序子序列中最大和。
例如：4, 2, 1, 5, 3
在这个序列中有如下的满足条件的升序子序列：
1) 4
2) 2
3) 1
4) 5
5) 3
6) 4, 5
7) 2, 5
8) 2, 3
9) 1, 5
10) 1, 3
显然最大的和是9.
Sample Input
5
4 2 1 5 3
Sample Output
9
寻求一个比较高效的算法，越详细越好。
大哥，我问的题目不至于那么傻吧。。。排序以后把顺序都改了还找什么子序列啊。。快速排序又不稳定，再说凭什么排序后要找最后两个呢？一楼的答案实在看不懂。。。
我原本考虑用dp策略和用并查集作临时最优解的数据结构，大家最好能不能再帮想一想。。
怎么都用排序。。。问题就是这样描述的。我再解释一下：
首先找出子序列(LCS问题中描述的子序列都理解吧),然后找出所有子序列中都是升序的，在这些升序的子序列中找出和最大的那个，不用给出那个序列，只要给出最大和就好。。
例如：4, 2, 1, 5, 3
在这个序列中有如下的满足条件的升序子序列：
1) 4
2) 2
3) 1
4) 5
5) 3
6) 4, 5
7) 2, 5
8) 2, 3
9) 1, 5
10) 1, 3
显然最大的和是9.
Sample Input
5
4 2 1 5 3
Sample Output
9
寻求一个比较高效的算法，越详细越好。
大哥，我问的题目不至于那么傻吧。。。排序以后把顺序都改了还找什么子序列啊。。快速排序又不稳定，再说凭什么排序后要找最后两个呢？一楼的答案实在看不懂。。。
我原本考虑用dp策略和用并查集作临时最优解的数据结构，大家最好能不能再帮想一想。。
怎么都用排序。。。问题就是这样描述的。我再解释一下：
首先找出子序列(LCS问题中描述的子序列都理解吧),然后找出所有子序列中都是升序的，在这些升序的子序列中找出和最大的那个，不用给出那个序列，只要给出最大和就好。。
这是一道典型的dp题，我用a[i]表示你给的n个数，用d[i]表示以第i的数为最后一个数的升序序列的最大和，那么我们有：
d[i] = max{ d[j] }+a[i] (j<i 并且 a[j] < a[i])
然后我们在d[i]中找到最大的一个就是答案
程序如下：
#include <iostream>
using namespace std;
int main(){
int d[100], a[100];
int n, i, j, ans;
scanf("%d", &n);
for (i = 0; i < n; ++i){
scanf("%d", &a[i]);
}
d[0] = a[0];
ans = 0;
for (i = 1; i < n; ++i){
d[i] = 0;
for (j = 0; j < i; ++j){
if (a[j] < a[i] && d[j] > d[i]){
d[i] = d[j];
}
}
d[i] += a[i];
if (d[i] > ans){
ans = d[i];
}
}
printf("%d\n", ans);
}
直接给分吧
把数据排序 1 2 3 4 5
最后两个不是最大了！
拜托，为什么现在的人问问题都不想着组织一下语言的呢？就不懂得把问题描述清楚？！“所有升序子序列的最大和”，你指的子序列规定了元素个数没有，如果没有的话，那么它本身也是自己的子序列啦~
我只能够猜你的意思是含两个元素的子序列的最大和了。程序，如下，希望是你的意思吧。
#include<stdio.h>