PAT Una suma máxima de subsecuencia de grado 1007

El tema es muy bueno:
da un rigor de los enteros K, una subsecuencia continua se define como ** {ni, ni + 1, …, nj} && 1 <= i <= j <= k **, la subsecuencia máxima es una subsecuencia continua del elemento más grande y la secuencia continua, y se obtiene el primer elemento, se obtiene el último elemento.

Entrar:
1 primera línea de un entero positivo K
2 segunda línea k enteros

Salida:
Esta subsecuencia continua y el primer elemento, el último elemento.
** Requisitos: ** Si esta sub-secuencia máxima no es única, el orden de salida es mínimo.
Si los números k son negativos, salida 0, el primer elemento de secuencia original, el último elemento

Idea:
Planificación dinámica, establezca una matriz NUM para almacenar este K digital, DP almacena la suma de los subsecuentes máximos.
Dp [i] se almacena en la suma de los subsecuentes máximos que terminan con NUM [i].
Ecuación de transferencia de estado:Dp[i]= max(num[i]Dp[i-1]+num[i])

Código:

#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int num[10005];
int dp[10005];
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    scanf("%d",&num[i]);
    dp[0]=num[0];
    for(int i=1;i<n;i++)
    {
        dp[i]=max(dp[i-1]+num[i],num[i]);
    }
    int k=0;
    for(int i=1;i<n;i++)/ / From a small to large enumeration, find the minimum order of the maximum subsequence
    {
        if(dp[i]>dp[k])
        k=i;
    }
    if(dp[k]<0)
    {
        printf("0 %d %dn",num[0],num[n-1]);// The maximum subsequence is a negative, the original sequence is affirm that it is negative
    }
    else
    {
        int sum=0;
        int index;
        for(int i=k;i>=0;i--)
        {
            sum+=num[i];
            index=i;
            if(sum==dp[k])
            {
                printf("%d %d %dn",dp[k],num[index],num[k]);
            }
        }
    }
    return 0;
}