这个解决问题的思路使用动态规划,即用已知状态去得到未知状态。
思路逻辑是这样 sum[i]记录以A[i]为末上升子序列的和的最大值
然后从j 从 0-i-1 遍历
如果A[j]<A[i] 那么 sum[i]=sum[j]+A[i];
然后找出sum[i]中的的最大值,就是以A[i]为末上升子序列的和的最大值。这样就实现了从前面状态到后面状态的推广。
#include<iostream>
#include<cstdlib>
using namespace std;
void coutmax(long sum[],int n){
long max=sum[0];
for(int i=1;i<n;i++){
if(sum[i]>max) max=sum[i];
}
cout << max <<'\n';
}
int main(){
int n=0;
while(cin >> n){
char c;
c=getchar();//读入换行
int* a=(int*)malloc(sizeof(int)*n);
long* maxsum=(long*)malloc(sizeof(long)*n);
for (int i=0;i<n;i++){
cin >> a[i];
maxsum[i]=a[i];
}
for(int i=1;i<n;i++){
for(int j=0;j<=i-1;j++){
if(a[i]>a[j]){
if(maxsum[j]+a[i]>maxsum[i]){
maxsum[i]=maxsum[j]+a[i];
}
}
}
}
coutmax(maxsum,n);
}
return 0;
}
结果: