首页 > 试题广场 >

最大上升子序列和

[编程题]最大上升子序列和
  • 热度指数：15570 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
一个数的序列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（可能重复）。


输出描述:
对于每组测试数据，输出其最大上升子序列和。
示例1

输入

7
1 7 3 5 9 4 8

输出

18
算法知识视频讲解
添加回答
C++
之一不之头像 之一不之 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a[maxn];
int dp[maxn];//dp[i]表示以i标号为末尾的上升子序列的和
int main(){
    int k;
    while(cin>>k){
        for(int i=0;i<k;i++){
            cin>>a[i];
        }
        int ans=0;
        for(int i=0;i<k;i++){
            dp[i]=a[i];
            for(int j=0;j<i;j++){
                if(a[j]<a[i]){
                    dp[i]=max(dp[i],dp[j]+a[i]);
                }
            }
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2021-09-01 20:28:35 回复(0)
求个好工作！头像 求个好工作！ 
#include<stdio.h>
int max(int x,int y);
int main()
{
    int n;
    while(scanf("%d",&n) != EOF)
    {
        int i,j,ans = 0;
        int num[n],dp[1000];
        for(i = 0;i < n;i++)
            scanf("%d",&num[i]);
        for(i = 0;i < n;i++)
        {
            dp[i] = num[i];
        }
        for(i = 1;i < n;i++)
        {
            for(j = 0;j < i;j++)
            {
                if(num[j] < num[i])
                {
                    dp[i] = max(dp[j] + num[i],dp[i]);
                }
            }
            if(dp[i] > ans)
            {
                ans = dp[i];
            }
        }
        printf("%d\n",ans);
    }
}


int max(int x,int y)
{
    if(x > y)
        return x;
    return y;
}

发表于 2020-03-18 16:54:09 回复(0)
C/C++
Dave_lzw头像 Dave_lzw 
// 最长上升 和 上升子序列最大和 不一样
#include <bits/stdc++.h>
using namespace std;
const int AX = 1e3 + 66 ;
int dp[AX];
int a[AX] ;
int n ;
int main() {
	while( ~scanf("%d",&n) ) {
		for( int i = 0 ; i < n ; i++ ) {
			scanf("%d",&a[i]);
		}
		dp[0] = a[0] ;
		int tot = 0 ;
		int id ; 
		for( int i = 1 ; i < n ; i++ ) {
			dp[i] = a[i] ;
			for( int j = 0 ; j < i ; j++ ) {
				if( a[j] < a[i] ) {
					if( dp[i] < dp[j] + a[i] ) {
						dp[i] = dp[j] + a[i] ;
					}
				}
			}
			tot = max( tot , dp[i] );
		}
		printf("%d\n",tot);
	}
	return 0 ;
}

发表于 2020-03-11 17:25:26 回复(0)
冲就完事了s头像 冲就完事了s 
#include <stdio.h>
(737)#include <stdint.h>

/* 
    最长上升子序列和

    在所有的上升子序列中,找到最大的子序列的和
    我们只需要记录,以 i 位置结束的位置, 所形成的最长子序列的和

    input:
        7
        1 7 3 5 9 4 8
    iuput:
        18


 */

#define N 1010
int arr[N];
int dp[N]; //  最长递增子序列

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    // freopen("data.txt", "r", stdin);
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
        }
        int maxVal = 0;
        for (int i = 0; i < n; i++)
        {
            dp[i] = arr[i];
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j])
                { // 满足递增的子序列, 记录下 dp[i] 是子序列的和
                    dp[i] = max(dp[i], dp[j] + arr[i]);
                    if (dp[i] > maxVal)
                    {
                        maxVal = dp[i];
                    }
                }
            }
        }
        printf("%d\n", maxVal);
    }

    return 0;
}

发表于 2020-03-05 14:45:35 回复(0)
月亮上的熊猫头像 月亮上的熊猫
动态规划主要考虑两点：
1.初始值。对于本题，可假设不存在升序子序列，即从位置0到位置 i 的最大升序子序列和为 arr[i] 自己。
2.状态转移。对于每一个arr[i] ，如果存在k<i ，即升序，则最大升序子序列和 = arr[i](自己) + res[k](0到 k 段的最大升序子序列和)。 
n = int(input())
arr = list(map(int,input().split()))
res = []
for k in range(n):
    res.append(arr[k])
for i in range(1,n):
    for j in range(i-1,-1,-1):
        if arr[j]<arr[i]:
            res[i] = max(res[i],arr[i]+res[j])
print(max(res))


发表于 2019-08-11 21:22:38 回复(0)
✭头像 ✭
#include<iostream>
using namespace std;
int dp[1000];
int num[1000];
int main(){
    int n;
    while(cin>>n){
        int i,j,k;
        //最大上升序列和
        for(i=0;i<n;i++){
            cin>>num[i];
            dp[i]=num[i];//最开始的时候，每个数自成一格最大上升序列
        }
        for(i=0;i<n;i++){
            for(j=i-1;j>=0;j--){
                if(num[j]<num[i])
                    dp[i]=max(dp[j]+num[i],dp[i]);
            }
        }
        int max_sum=dp[0];
        for(k=0;k<n;k++){//取dp中最大值，则为最大上升序列和
            if(dp[k]>max_sum)
                max_sum=dp[k];
        }

        /*
        //最长连续上升子序列
        for(i=0;i<n;i++){
                cin>>num[i];
                dp[i]=1;//最开始的时候，dp[i]赋初值0
        }
        for(i=1;i<n;i++){
            if(num[i-1]<num[i])
                dp[i]=max(dp[i-1]+1,dp[i]);
        }
        int max_sum=dp[0];
        for(k=0;k<n;k++){//取dp中最大值，则为最长连续上升子序列
            if(dp[k]>max_sum)
                max_sum=dp[k];
        }
        */
        cout<<max_sum<<endl;
    }
    return 0;
}

发表于 2019-03-15 11:33:30 回复(0)
C/C++
保洁大哥头像 保洁大哥
#include <iostream>
#include<memory.h>
using namespace std;
long maxn[1010];
int main()
{int n;
while(cin>>n){
     int *a=new int[n];
     for(int i=0;i<n;i++)cin>>a[i];//输入序列
     maxn[0]=a[0];
     for(int i=1;i<n;i++)
     for(int j=i-1;j>=0;j--){
          if(a[i]>a[j]){maxn[i]=(maxn[i]>maxn[j]+a[i])?maxn[i]:(maxn[j]+a[i]);}//求每个位置的最大
     }
     int max=0;
     for(int i=0;i<n;i++){
          if(maxn[i]>max)max=maxn[i];//求最大和
     }
     cout<<max<<endl;
}
return 0;
}

发表于 2019-03-04 10:56:43 回复(2)
已注销头像 已注销 
#include<stdio.h>
int main()
{
 int n,i,j;
 scanf("%d",&n);
 int num[n],sum[n];
 for(i=0;i<=n-1;i++)
 {
  scanf("%d",&num[i]);
  sum[i]=num[i];
 }
 int max=num[0];
 for(i=1;i<=n-1;i++)
 {
  for(j=0;j<=i-1;j++)
  {
   if(num[i]>num[j])
   {
    if(num[i]+sum[j]>sum[i])
    {
     sum[i]=num[i]+sum[j];
    }
   }
  }
 }
 for(i=0;i<=n-1;i++)
 {
  if(max<sum[i])
  max=sum[i];
 }
 printf("%d",max);
 return 0;
}

发表于 2018-11-14 16:24:49 回复(0)
小渣渣渣渣渣渣头像 小渣渣渣渣渣渣 
while 1:
    try:
        n=int(input())
        kk=list(map(int,input().split(" ")))
        l=[0]*n
        for i in range(n):
            mm=0
            for j in range(i):
                if kk[j]<kk[i]:
                    mm=max(l[j],mm)
            l[i]=mm+kk[i]
        print(max(l))
    except:
        break


	


很简单，就是过不了。。本地过，牛客说我输出空。有大佬指点一下么

发表于 2018-04-07 09:33:05 回复(2)
Benson666头像 Benson666 
动态规划问题
import java.util.Scanner;
public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int[] arr = new int[n];
            int[] dp = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = in.nextInt();
                dp[i] = arr[i];
            }
            for(int i=1;i<n;i++){
                for(int j=i-1;j>=0;j--){
                    if(arr[i]>arr[j])
                        dp[i] = Math.max(dp[i], arr[i]+dp[j]);
                }
            }
            int max= dp[0];
            for(int i=1;i<n;i++)
                max = Math.max(max,dp[i]);
            System.out.println(max);
        }
    }
}

编辑于 2018-03-07 12:03:02 回复(0)
C/C++
_stormpang头像 _stormpang 
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn = 1001;

int num[maxn];
int mymax[maxn];    // mymax[i] 表示 以 num[i] 结尾的子序列的最大值

int main()
{
    int n;
    while(cin >> n)
    {
        memset(mymax, 0, sizeof(mymax));

        for(int i = 0; i < n; ++i)
        {
            cin >> num[i];
        }

        int max = num[0];
        for(int i = 0; i < n; ++i)
        {
            mymax[i] = num[i];
            for(int j = 0; j < i; ++j)
            {
                if(num[j] < num[i] && mymax[j]+num[i] > mymax[i])
                {
                    mymax[i] = mymax[j]+num[i];
                }
            }
            if(mymax[i] > max)
            {
                max = mymax[i];
            }
        }
        cout << max << endl;
    }
    return 0;
}


发表于 2016-08-10 10:25:41 回复(0)
chenxd头像 chenxd
C++语言： 
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int num[1001];
    int sum[1001];
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>num[i];
            sum[i] = num[i];
        }
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;--j){
                if(num[j]<num[i]){
                    sum[i] = max(sum[i],sum[j]+num[i]);
                }
            }
        }
        int max = 0;
        for(int i=0;i<n;i++){
            if(sum[i]>max)
                max = sum[i];
        }
        cout<<max<<endl;
    }
    return 0;
}

发表于 2019-02-03 19:27:32 回复(0)
C/C++
kestars头像 kestars 
//还是动态规划，在上一题的基础上进行改进。注意是严格单调递增
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int k;
    while(scanf("%d",&k)!=EOF){
        vector<int> height(k,0);
        for(int i=0;i<k;i++){
            scanf("%d",&height[i]);
        }
        vector<int> dp(k);
        for(int i=0;i<k;i++){
            dp[i]=height[i];
        }
        int maxVal=height[0];
        
        for(int i=1;i<k;i++){
			int temp=0;
            for(int j=i;j>0;j--){
                if(height[i]>height[i-j]){
                    temp=max(temp,dp[i-j]);
                }
            }
			dp[i]=dp[i]+temp;
            if(maxVal<dp[i]){
                maxVal=dp[i];
            }
        }
        printf("%d\n",maxVal);
    }
}

发表于 2016-10-26 22:42:46 回复(0)
C/C++
www_helloworld_cn头像 www_helloworld_cn

动态规划求解
开始假设所有的数自成最大递增子序列，也就是sum[i]=num[i]；
后面再从前向后遍历，如果前面某个数小于当前的数，那么那个数的最大递增子序列的和加上当前的数会构成更大的递增子序列和，找出所有这样的和的最大值作为以当前数为尾的最大递增子序列的和。

#include <iostream>
using namespace std;

int main()
{
    int n;
    int num[1001];
    int sum[1001];
    while(cin>>n)
    {
        int tmpsum = 0, maxsum = 0;
        for(int i = 0; i<n; i++)
        {
            cin>>num[i];
            sum[i] = num[i]; //初始化，所有数自成一个最大递增子序列
        }
        sum[0] = num[0];
        for(int i = 1; i<n; i++)
        {
            for(int j = i-1; j>=0; j--)
            {
                if(num[j]<num[i])   //符合递增子序列
                    sum[i] = max(sum[j]+num[i], sum[i]);
            }
        }
        maxsum = sum[0];
        for(int i = 1; i<n; i++)
        {
            if(maxsum<sum[i]) maxsum = sum[i];
        }
        cout<<maxsum<<endl;
    }
    return 0;
}
发表于 2018-03-05 17:27:45 回复(1)
C/C++
idutura头像 idutura 
/*
    动态规划，是最长递增子序列的一个变形
	dp[i] 表示以a[i]为结尾的最长递增子序列的和
	1.如果a[i]之前的都比a[i]大，那么和就为自身的大小
	2.如果a[i]之前有比它小的a[j]，那么就将a[i]添加到
	以a[j]为结尾的序列的末尾，这样就是a[i]的最长公共子序列和
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int dp[maxn];
int arr[maxn];
int main() {
	int n;
	while(~scanf("%d",&n)) {
		for(int i=0; i<n; i++) { // input
			scanf("%d",&arr[i]);
			dp[i] = arr[i]; // 默认所有数自己本身是一个递增序列
		}
		int ans = INT_MIN;
		for(int i=0; i<n; i++) {
			for(int j=0; j<i; j++) { // 找在i之前有没有比i小的
				if(arr[j]<arr[i]) {
					dp[i] = max(dp[j]+arr[i],dp[i]);
				}
				ans = max(ans,dp[i]);
			}
		}
		printf("%d\n",ans);
	}
}

编辑于 2020-03-23 20:58:58 回复(1)
啥头像 啥
貌似测试代码的上升序列是单调上升，而不是单调不减，不符合题意的说明
发表于 2016-05-01 13:09:18 回复(1)
C/C++
猫猫猫1头像 猫猫猫1
#include<bits/stdc++.h>
using namespace std;

const int Max=1000;
int a[Max];
int dp[Max];

int main() {
    int n;
    while(cin>>n) {
        for(int i=0; i<n; i++) {
            cin>>a[i];
        }
        int answer=0;
        for(int i=0; i<n; i++) {
            dp[i]=a[i];
            for(int j=0; j<i; j++) {
                if(a[j]<a[i]) {
                    dp[i]=max(dp[i],dp[j]+a[i]);
                }
            }
            answer=max(answer,dp[i]);
        }
        cout<<answer<<endl;
    }
    return 0;
}
发表于 2022-10-16 14:24:19 回复(1)
牛客724164131号头像 牛客724164131号 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        vector<int>nums(n);
        for(int i=0;i<n;i++){
            cin>>nums[i];
        }
        vector<int>dp(n);
        dp[0]=nums[0];
        int ans=dp[0];
        for(int i=0;i<n;i++){
            dp[i]=nums[i];
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[j]+nums[i],dp[i]);
            
                }
                ans = max(dp[i],ans);
            }
        }
        cout<<ans<<endl;
    }
}

发表于 2025-03-24 13:08:15 回复(0)
牛客485262153号头像 牛客485262153号
本题求的是最大上升子序列和，其原理与求最长递增子序列的原理完全一致，只是状态转
移方程相应地发生了一些变化，原来 dp[i]是以 A[i]作为末尾的最长递增子序列的长度，现在
将 dp[i]变成了以 A[i]作为末尾的最大上升子序列和。 
#include <cstdio>
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main() {
    int s[1000];
    long long int dp[1001];
    int n;
    while (scanf("%d",&n)!=EOF) {
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++){
            scanf("%d",&s[i]);
        }
        long long int m=s[0];
        for(int i=0;i<n;i++){
            dp[i]=s[i];
            for(int j=0;j<i;j++){
                if(s[j]<s[i]){
                    //dp包含j坐标的最大上升子序列和
                    dp[i]=max(dp[i],dp[j]+s[i]);
                }
            }
            m=max(m,dp[i]);
        }
    printf("%lld",m);
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-03-23 13:35:59 回复(0)
C++
霜降Frostine头像 霜降Frostine
dp 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    while(cin>>n){
        vector<int> nums(n);
        for(int i = 0; i < n; i++){
            cin>>nums[i];
        }

        vector<int> dp(n, 0);
        for(int i = 0; i < n; i++){
            dp[i] = nums[i];
        }

        int max_len = INT_MIN;

        for(int i = 1; i < n; i++){
            int tmp = dp[i];
            for(int j = 0; j < i; j++){
                if(nums[j]<nums[i]){
                    dp[i] = max(dp[i], tmp + dp[j]);
                }
            }         
            if(dp[i]>max_len) max_len = dp[i];
        }
        
        cout<<max_len<<endl;
    }
}

发表于 2025-03-12 21:22:58 回复(0)
提交观点

问题信息

动态规划
难度：
84条回答 15542浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大上升子序列和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号