PTA Maximum Subsequence Sum

Question

#include <stdio.h>
#include <stdlib.h>
#define element int

int main()
{
    int cnt;
    int flag2 = 0;
    scanf("%d", &cnt);
    element* Q = (element*)malloc(sizeof(element) * cnt);
    for (int i = 0; i < cnt; i++)
    {
        scanf("%d", &Q[i]);
        if (Q[i] > 0) flag2 = 1;
    }
    int sum = -1;
    int currentsum = 0;
    int head = 0;
    int last = cnt - 1;
    int finalhead = 0;
    int finallast = cnt - 1;
    int finalsum = 0;
    int flag = 0;
    for (int i = 0; i < cnt; i++)
    {
        currentsum += Q[i];
        if (!flag2 && currentsum == 0)
        {
            finalhead = i;
            finallast = i;
        }
        if (currentsum > sum)
        {
            sum = currentsum;
            if (!flag)
            {
                head = i;
                flag = 1;
            }
            last = i;
        }
        if (currentsum < 0)
        {
            currentsum = 0;
            if (sum > finalsum)
            {
                finalhead = head;
                finallast = last;
                finalsum = sum;
            }
            flag = 0;
        }
    }
    if (sum > finalsum)
    {
        finalsum = sum;
        finalhead = head;
        finallast = last;
    }
    printf("%d %d %d", finalsum, Q[finalhead], Q[finallast]);
    free(Q);
    return 0;
}

求大神指导，测试点2为啥通不过，例如输入
4
0 1 2 0
可以成功输出 3 0 2

Answer 1

最大子列和 用在线处理不就行了。

int MaxSubseqSum4( int A[], int N ) {
    int ThisSum, MaxSum, i;
    
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ ) {
          ThisSum += A[i]; /* 向右累加 */
          if( ThisSum > MaxSum )
                  MaxSum = ThisSum; /* ·发现更大和则更新当前结果 */
          else if( ThisSum < 0 ) /* 如果当前子列和为负数 */
                  ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */
    }
    
    return MaxSum;  
}