最大上升子序列和

//最大上升子序列和
//dp[i]:包含a[i]在内的前i个元素的最大上身子序列和
//input：7
//1 7 3 5 9 4 8
//output
//18
#include<bits/stdc++.h>
using namespace std;

int n;
int a[100];
int dp[100];

int main()
{
   scanf("%d",&n);
   for(int i=0;i<n;i++)
   {
       scanf("%d",&a[i]);
   }
   dp[0] = a[0];
   for(int i=1;i<=n;i++)
   {
       dp[i] = -1;
       for (int j = 0; j < i; j++)
       {
           if (a[i] > a[j] )
           {
               int mid = dp[j] + a[i];
               dp[i] = max(mid,dp[i]);//统计最大值
           }
       }
   }
   for(int i=0;i<n;i++)
   {
       printf("%d ",dp[i]);
   }
}