Description
给定长度为n的正整数序列a1,a2,…,an。
令sum=ab1+ab2+…+abm，并且满足：ab1<ab2<…<abm；b1<b2<…<bm;1<=m<=n。
求最大的sum。
n<=1000,0<ai<=109
Input
第一行，n，表示给定序列的个数。
第二行，n个用空格隔开的正整数序列。
Output
最大的sum。
Sample Input
6
2 4 1 20 5 6
Sample Output
26
思路：这道题的思路和最长上升子序列一样，但是需要稍加改动。排序的时候一直没把int改为ll，一直wa，好难过。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <
string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
using namespace std;
#define ll long long
const int inf =
0x3f3f3f3f;
const int mod = 1e9+
7;
int n, num[
1000+
8];
ll dp[1000+
8];
int main()
{
scanf("%d", &
n);
for(
int i =
0; i<n; i++
)
{
scanf("%d", &
num[i]);
dp[i] =
num[i];
}
for(
int i =
0; i<n; i++
)
for(
int j =
0; j<i; j++
)
if(num[i]>num[j] && dp[j]+num[i]>dp[i])dp[i] = dp[j]+
num[i];
sort(dp, dp+n, greater<ll>
());
printf("%lld\n", dp[
0]);
return 0;
}
转载于:https://www.cnblogs.com/RootVount/p/11265080.html
相关资源：JAVA上百实例源码以及开源项目
