首页 > 试题广场 >

最大上升子序列和

[编程题]最大上升子序列和
  • 热度指数:13907 时间限制: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
头像 大内高手
发表于 2020-03-17 18:38:09
最长递增子序列的变形问题。 // runtime: 4ms // space; 496K #include <iostream> #include <cstdio> using namespace std; const int MAX = 1000; int arr[MAX 展开全文
头像 普罗列塔丽亚
发表于 2022-02-12 01:17:47
【最长递增子序列】 dp[i]表示“以i结尾”(指必须取num[i])的最长递增子序列长度,因此结果可以累加到dp[n],直接取dp[n]即可 【最大递增子序列和】 dp[i]表示“从0到i”(可以不取num[i])的最大递增子序列和,各自结果独立,因此需要求max 展开全文
头像 在做毕设的鲸鱼很刻苦
发表于 2023-03-04 16:17:29
#include <iostream> #include <algorithm> using namespace std; int main() { int n; int a[1001], dp[1001]; while (cin >> 展开全文
头像 在考古的小鱼干很有气魄
发表于 2023-03-09 10:15:05
#include <bits/stdc++.h> #define MAX 1000 using namespace std; int main() { int dp[MAX], data[MAX]; int n; while (cin >> n) { 展开全文
头像 Huster水仙
发表于 2023-02-10 15:09:26
最大上升子序列和(不一定连续) 思路:统计以s[i]结尾的上升子序列的和sum[i] 分为2类:是否比前面所有元素都小 ①是 前面序列对其没有贡献:sum[i]=s[i] ②否 前面序列对其有贡献:sum[i]=max(sum[j]+s[i])(需遍历s[i]前面所有元素,保留最大值) #inc 展开全文
头像 Perceive109
发表于 2023-03-25 15:06:41
#include "iostream" #include "vector" using namespace std; // 思路:Dp数组问题经典思路-从后往前 // 从倒数第二个元素开始,不断找后面元素比自己的的元素,随后判断:max(自己、dp[比自己大的元素]),作为dp[自己] // 如: 展开全文
头像 辣椒味的糖葫芦
发表于 2023-03-18 18:59:20
n = int(input()) num = list(map(int, input().split(" "))) dp = list(num)#记住,一定要加个list(),否则就是同一个内存地址 for i in range(n): for j in range(i): 展开全文
头像 笑川不吃香菜
发表于 2024-03-15 15:38:55
#include <bits/stdc++.h> using namespace std; int main() { int n;cin>>n; int arr[n],dp[n]; for(int i =0;i<n;i++) dp 展开全文
头像 鱼儿恋上水
发表于 2020-05-21 20:41:56
/* 状态转移方程 sum[i] = max{1, sum[j] + 1} i < j and A[i] > A[j] 边界 sum[i] = A[i] (i = 1, 2, ... n) */ #include <algorithm> #include <cstdio 展开全文
头像 爱喝零度可乐
发表于 2023-03-15 17:02:36
#include<iostream> #include<cstdio> using namespace std; int a[1010]; int dp[1010]; int main() { int n; while (scanf("%d", &n) != 展开全文