最大上升子序列和

Question

一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中序列和最大为18，为子序列(1, 3, 5, 9)的和. 你的任务，就是对于给定的序列，求出最大上升子序列和。注意，最长的上升子序列的和不一定是最大的，比如序列(100, 1, 2, 3)的最大上升子序列和为100，而最长上升子序列为(1, 2, 3)。
下面是我的代码，没有AC，想问一下问题在哪
请输入代码

include<stdio.h>

int max(int a,int b){

return a>b? a:b;

}
int dp[1000];
int list[1000];
int main(){

int n;
while(~scanf("%d",&n)){       
    for(int i=0;i<n;i++)
        scanf("%d",&list[i]);
    dp[0]=list[0];
    for(int i=1;i<n;i++){
        int tmax=dp[0];
        for(int j=0;j<i;j++){
            if(list[i]>list[j]&&dp[j]>tmax){
                tmax=dp[j];
            }
        }
        dp[i]=tmax+list[i];
    }
    int max=-123123123;
    for(int i=0;i<n;i++){
        if(dp[i]>max){
            max=dp[i];
        }
    }
    printf("%d\n",max);
    
    
}

}

Answer 1

输入3个数 2，1，2你的返回值是5 明显不对啊

    for(int i=1;i<n;i++){
        int tmax=0;    //不是dp[0]，list[1]<list[0] 的话dp[1] = 0 + list[1]
        for(int j=0;j<i;j++){
            if(list[i]>list[j]&&dp[j]>tmax){
                tmax=dp[j];
            }
        }
        dp[i]=tmax+list[i];
    }