2958. 求上升子序列和的最大值

动态规划。思路：到第i个数为止的最大上升子序列的和等于到第i-1个数为止、且最大数字小于第i个数的最大上升子序列的和+第i个数字。
建立一维数组存储最大数字为x的最大上升子序列的和（初始化0），每次查找其中前y个值的最大值即可。
附C代码：

#include <stdio.h>
int getMax(int *a, int b)
{
    int i, max=0;
    for(i=0; i<b; i++, a++)
        if(*a>max)
            max=*a;
    return max;
}
int main()
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, i, num[5000], ans[4000]={0}, k;
        scanf("%d",&n);
        for(i=0; i<n; i++) scanf("%d",&num[i]);
        for(i=0; i<n; i++)
        {
            k=num[i];
            ans[k]=getMax(ans, k)+k;
        }
        printf("case #%d:\n%d\n",I,getMax(ans,4000));
    }
    return 0;
}

经典动态规划题，极具收藏价值
关键词:“最长上升子序列”

对于每一个数，它前面的，比它小的数为结尾的最长上升子序列的和，再加上它本身的值，就是以这个数结尾的最长上升子序列的和的值。

注意初始化，以每一个数结尾的最长上升子序列的和，至少为它本身（只取这个数自己）

include

using namespace std;
int T,n;
int a[5010];
int dp[5010];
int main()
{
std::ios::sync_with_stdio(false);
cin>>T;
for(int step=0;step>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i]=a[i]; //注意初始化，以每一个数结尾的最长上升子序列的和，至少为它本身（只取这个数自己）
}
int Max=a[1];
for(int i=1;i<=n;i++)
for(int j=1;j<=i-1;j++)
if(a[i]>a[j])
{
dp[i]=max(dp[i],dp[j]+a[i]);
Max=max(Max,dp[i]);
}
printf(“case #%d:\n%d\n”,step,Max);
}
return 0;
}

子序列中最大值最大对应的子序列之和不一定最大。。。

前面发的都是些什么东西……

void solve(int a[],int n){
int dp[maxn];
int re=0;
memset(dp, 0, sizeof(dp));
for(int i=0;i<n;i++){
dp[i]=a[i];
for(int j=0;ja[j] && dp[i]<a[i]+dp[j])
dp[i]=a[i]+dp[j];
}
re=max(re,dp[i]);
}
cout<<re<<endl;
}

int main(int argc, const char * argv[]) {
int cas;
cin>>cas;
for(int i=0;i>n;
for(int j=0;j<n;j++)
scanf(“%d”,&a[j]);
printf(“case #%d:\n”,i);
solve(a,n);
}
return 0;
}

升序 >

超时……why??!
有无大佬救救我，急急急，不在线等orz
用的Python3
n=int(input())
for i in range(n):
weishu=int(input())
line=input().split(‘ ‘)
line=[int(j) for j in line]
alllist=[]
for k in range(len(line)): #建立循环，遍历子序列
partlist=[]
partlist.append(line[k])
num=k
target=line[k]
while num0: if target>line[num-1]:
partlist=[line[num-1]]+partlist
num-=1
target=line[num]
else:
num-=1
alllist.append(partlist)
maxnum=sum(alllist[0])
for x in range(1,len(alllist)):#求出最大序列和
if sum(alllist[x])>maxnum:
maxnum=sum(alllist[x])
print(‘case #{}:’.format(i))
print(maxnum)

include

/真的算是很经典入门的动态规划了，注意是子序列（不要求连续），不是子串（要求连续）/

include

using namespace std;
int getMax(int a,int b){
return a>b?a:b;
}
int main(){
int T;
cin>>T;
int max;
for(int i =0;i>n;
int nums[n];
int dp[n];
for(int i =0; i>nums[i];
}
for(int i =0;i<n;i++){
max = nums[i];
for(int k = 0;knums[k]){
max = getMax(max,dp[k]+nums[i]);
}

        }
        dp[i] = max;
    }
    printf("case #%d:\n",i);
    int myreturn = -1;
    for(int i =0;i<n;i++){
        myreturn = (myreturn>dp[i])?myreturn:dp[i];
    } 
    cout<<myreturn<<endl;

}

}

输出少输了一个”:”，哇了5发…
菜的想把自己砍死…

题目第一句什么鬼