hdu1087 Super Jumping! Jumping! Jumping!(LIS)

단순 LIS

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 1005
int dp[maxn],a[maxn];
int main()
{
    int t;
    int i,j;
    int ans;
    while(~scanf("%d",&t)&&t)
    {
        memset(dp,0,sizeof(dp));
        for(i=1;i<=t;i++)
        {
            scanf("%d",&a[i]);

        }
        a[0]=-inf;
        for(i=1;i<=t;i++)
        {
            ans=-inf;
            for(j=0;j<i;j++)
            {
                if(a[i]>a[j])
                    ans=max(ans,dp[j]);
            }
            dp[i]=ans+a[i];
        }
        ans=-inf;
        for(i=1;i<=t;i++)
            ans=max(ans,dp[i]);
        printf("%d
",ans);
    }
    return 0;
}