今天决定掉头撸dp。。

在网上找了文章，，大概讲了这题，，

一个有N个元素的整型数组arr，有正有负，数组中连续一个或多个元素组成一个子数组，这个数组当然有很多子数组，求子数组之和的最大值。例如：[0，-2，3，5，-1，2]应返回9，[-9，-2，-3，-5，-3]应返回-2。

然后，，给出的代码是

/* DP base version*/ #define max(a,b) ( a > b ? a : b)   int Maxsum_dp(int * arr, int size) {      int End[30] = {-INF};      int All[30] = {-INF};      End[0] = All[0] = arr[0];        for(int i = 1; i < size; ++i)      {          End[i] = max(End[i-1]+arr[i],arr[i]);          All[i] = max(End[i],All[i-1]);      }      return All[size-1]; } 然后我想起来了几个月前我做的一道题 题目描述 Description

给一个数组a1, a2 ... an，找到最长的上升降子序列ab1<ab2< .. <abk，其中b1<b2<..bk。

输出长度即可。

输入描述 Input Description

第一行，一个整数N。

第二行 ，N个整数（N < = 5000）

输出描述 Output Description

输出K的极大值，即最长不下降子序列的长度

样例输入 Sample Input

5

9 3 6 2 7

样例输出 Sample Output

3

然后我的代码是这样子的，，

#include<iostream> #include<algorithm> using namespace std; struct node{ int id,num,mx; }a[5000]; int main() { int n,mx=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].num;a[i].id=i;a[i].mx=1; }int v=1; for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++) { if(a[j].num<=a[i].num){continue;} else{a[i].mx++;a[i].num=a[j].num;} }v=(v>a[i].mx)? v:a[i].mx; } cout<<v; return 0; } 感觉好暴力啊，，但是跑得还挺快ORZ。