LIS
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 1010; int dp[MAXN],a[MAXN]; inline int Max(int a,int b){ return a>b?a:b; } int main(){ int n; while(~scanf("%d",&n),n){ memset(dp,0,sizeof(dp)); for(int i = 1;i <= n;i++){ scanf("%d",&a[i]); } int m; m = dp[1] = a[1]; for(int i = 2;i <= n;i++){ dp[i] = a[i]; for(int j = 1;j <= i;j++){ if(a[i] > a[j]){ dp[i] = Max(dp[i],dp[j] + a[i]); } } m = Max(m,dp[i]); } printf("%d\n",m); } return 0; }