频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
题目1480:最大上升子序列和
2013-03-26 08:11:53           
收藏   我要投稿
题目1480:最大上升子序列和时间限制:1 秒

内存限制:128 兆

特殊判题:否

提交:562

解决:175

 

题目描述:

一个数的序列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)等等。这些子序列中序列和最大为18,为子序列(1, 3, 5, 9)的和.

 

你的任务,就是对于给定的序列,求出最大上升子序列和。注意,最长的上升子序列的和不一定是最大的,比如序列(100, 1, 2, 3)的最大上升子序列和为100,而最长上升子序列为(1, 2, 3)。

 

输入:

输入包含多组测试数据。

每组测试数据由两行组成。第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000(可能重复)。

 

输出:

对于每组测试数据,输出其最大上升子序列和。

 

样例输入:

7

1 7 3 5 9 4 8样例输出:

18来源:

2012年北京大学计算机研究生机试真题

 

 

 

[cpp] 

/********************************* 

*   日期:2013-3-25 

*   作者:SJF0115 

*   题号: 题目1480:最大上升子序列和 

*   来源:https://ac.jobdu.com/problem.php?pid=1480 

*   结果:AC 

*   来源:2012年北京大学计算机研究生机试真题 

*   总结: 

**********************************/  

#include<stdio.h>   

#include<string.h>   

  

int array[1010];  

int Max[1010];  

  

void LIS(int k){  

    memset(Max,0,sizeof(Max));  

    for(int i = 1;i <= k; i++){  

        Max[i] = array[i];  

        //和i号数据之前的数据比较   

        for(int j = 1;j < i;j++){  

            if(array[i] > array[j]){  

                if(Max[i] < Max[j] + array[i]){  

                    Max[i] = Max[j] + array[i];  

                }  

            }  

        }  

    }  

}  

   

int main()  

{  

    int N,i;  

    //freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);   

    while(scanf("%d",&N)!=EOF){  

        //输入数据   

        for(i = 1;i <= N;i++){  

            scanf("%d",&array[i]);  

        }  

        LIS(N);  

        //输出最大值   

        int MaxValue = -1;  

        for(i = 1;i <= N;i++){  

            if(MaxValue < Max[i]){  

                MaxValue = Max[i];  

            }  

        }  

        printf("%d\n",MaxValue);  

    }  

    return 0;  

}  

 

/*********************************

*   日期:2013-3-25

*   作者:SJF0115

*   题号: 题目1480:最大上升子序列和

*   来源:https://ac.jobdu.com/problem.php?pid=1480

*   结果:AC

*   来源:2012年北京大学计算机研究生机试真题

*   总结:

**********************************/

#include<stdio.h>

#include<string.h>

 

int array[1010];

int Max[1010];

 

void LIS(int k){

memset(Max,0,sizeof(Max));

for(int i = 1;i <= k; i++){

Max[i] = array[i];

//和i号数据之前的数据比较

for(int j = 1;j < i;j++){

if(array[i] > array[j]){

if(Max[i] < Max[j] + array[i]){

Max[i] = Max[j] + array[i];

}

}

}

}

}

 

int main()

{

int N,i;

//freopen("C:\\Users\\SJF\\Desktop\\acm.txt","r",stdin);

while(scanf("%d",&N)!=EOF){

//输入数据

for(i = 1;i <= N;i++){

scanf("%d",&array[i]);

}

LIS(N);

//输出最大值

int MaxValue = -1;

for(i = 1;i <= N;i++){

if(MaxValue < Max[i]){

MaxValue = Max[i];

}

}

printf("%d\n",MaxValue);

}

return 0;

}

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 升子 序列 题目
上一篇:西电1228 最大匹配 二分匹配求最大的组数
下一篇:西电1232 求斐波拉契数列的后四位
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站