传送门：

 

解题思路：

这是单最长调递增子序列的一个变形

d[i]:表示以a[i]结尾的序列和的最大值。

因此定义下面的状态方程：

在初始以d[i]结尾的序列只有a[i]一个，因此d[i]=a[i].

实现代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int MAXN=2005;const int INF=1<<20;int End,n;int a[MAXN];int dp[MAXN];/******************************************dp[i]：表示以a【i】结尾，单调递增序列和的最大值******************************************/void solve(){    int res=-INF;    for(int i=0;i