这题错的莫名其妙

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define MAXN 1000+5

using namespace std;

int a[1005];

int dp[1005];

int main(void)

{

         intn;

         while((scanf("%d",&n))==1&&n)

         {

         for(inti=1;i<=n;i++)

         {

                   scanf("%d",&a[i]);

                   dp[i]=a[i];

         }

         for(inti=2;i<=n;i++)

         {

                   intmmax=-99999;

                   for(intj=1;j<i;j++)

                   {

                            if(a[j]<a[i]&& a[j] >= mmax)

                            {

                                     mmax= a[j];

                            }

                   }

                   //printf("%d-",index);

                   if(index!=-1)

                   dp[i]+=dp[index];

                   //printf("%d-",dp[i]);

         }

         int  mmax=-999999;

         for(inti=1;i<=n;i++)

         {

                   if(dp[i]>mmax)

                            mmax=dp[i];

         }

         printf("----%d\n",mmax);

         }

}


AC了，发现还是思维错了，求的应该是 a[i] < a[i] 中 DP 最大的 ，而不是 a[j] < a[i] 中，，最大的数，， 对应的  DP 。 比如例子  7 1 2 3 4 5 6 8  如果按照上面的会输出 15 ，然而应该是 1+2+3+4+5+6+8 是最大值 。    这题可以简单的说，我只要找出比 a [i] 小的d[j]集合中  ， dp最大的那个 。。 必定满足每次都是最大，那么dp[1~n] 每一个都是最优的情况，那么推出  dp[n]就是最优的情况. 就满足了最优子解的问题。再者考虑 无后效性 ，  前面我选择了什么，只能通过当前的状态去影响后面的状态，而不能持续的影响以后的状态，  我通过哪个dp  找到当前的 dp[i] 无所谓（4  3 1 5，DP[4]无论是从4→5还是3→1→5，对于5后面的DP没有任何影响），我只要找到DP最大的，并且小于a[i]的就满足要求就可以。 ````````` 也就这么粗浅的理解了，还需要多做题来理解题目意思`````。动态规划就是说要求 每一个DP 都是 最优，每一个DP都是由前面的最优DP推出来，当前的求得的DP由前面最优的DP求出来，当前的DP也就是最优的，每一个DP是最优的，最终所求的DP[N]就是最优解了1！！！！！。 这题和最长上升序列几乎一样

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 1000+5

using namespacestd;

int a[10005];

int dp[10005];

int main(void)

{

    int n;

    while((scanf("%d",&n))==1&&n)

    {

    for(int i=1;i<=n;i++)

    {

       scanf("%d",&a[i]);

       dp[i]=a[i];

    }

    dp[1]=a[1];

    for(int i=2;i<=n;i++)

    {

       int mmax=0;

       int index=-1;

       for(int j=1;j<i;j++)

       {

           if(a[j]<a[i] && dp[j]>= mmax)

           {

              mmax = dp[j];

              index = j;

           }

       }

       //printf("%d-",index);

       dp[i]+=mmax;

       //printf("%d-",dp[i]);

    }

    int mmax=-999999;

    for(int i=1;i<=n;i++)

    {

       //printf("%d-",dp[i]);

       if(dp[i]>mmax)

           mmax=dp[i];

    }

    printf("%d\n",mmax);

    }

}