연속 부분 수열의 최대 합 문제

문제 설명: 주어진 시퀀스 a[1],a[2]...a[n]에서 연속된 하위 시퀀스에 있는 요소 합계의 최대값을 찾습니다.
예: 6 -1 5 4 -7 이 시퀀스의 최대 연속 하위 시퀀스 합은 14입니다.
구체적인 질문은 HDOJ 1003 TZU 1202를 참조하세요.
이 질문은 "Data Structure and Algorithm Analysis--C Language Description"(Weiss 작성)에 있습니다. 중국어 버전 13페이지(영어 버전) 18페이지에도 설명되어 있습니다. 21페이지에 알고리즘 프로그램이 나와 있습니다.

int MaxSubsequenceSum(const int A[], int N)  
{  
  int ThisSum,MaxSum,j;  
  ThisSum = MaxSum = 0;  
  for(j = 0; j < N; j++)  
  {  
    ThisSum += A[j];  
    if(ThisSum > MaxSum)  
      MaxSum = ThisSum;  
    else if(ThisSum < 0)  
      ThisSum = 0;  
   }  
  return MaxSum;  
}

알고리즘을 다음과 같이 작성했습니다.

int MaxSubsequenceSum(const int A[], int N)  
{  
  int ThisSum,MaxSum,j;  
  ThisSum =0， MaxSum =INT_MIN;  
  for(j = 0; j < N; j++)  
  {  
    ThisSum += A[j];  
    if(ThisSum > MaxSum)  
      MaxSum = ThisSum;  
    if(ThisSum < 0)  
      ThisSum = 0;  
   }  
  return MaxSum;  
}

이때, else 키워드를 삭제해야 하는 이유는 변수를 초기화하기 위해 다른 값을 사용했기 때문입니다. 책의 예를 통해 MaxSum이 음수가 아닌지 항상 확인할 수 있습니다. 내가 다시 작성한 알고리즘에서 MaxSum은 많은 경우에 음수가 됩니다.
내 acm 프로그램은 다음과 같습니다(위의 두 웹사이트는 모두 ac입니다).

#include <stdio.h>  
#include <limits.h>  
  
#define MAX 100000+100  
  
int main(void)  
{  
  int n;  
  int m;  
  int a[MAX];  
  int i,j;  
  int thisSum,maxSum;  
  int maxStart,maxEnd,thisStart;  
  
  scanf("%d",&n);  
  for(i = 1; i <= n; i++)  
    {  
      scanf("%d",&m);  
      for(maxStart=maxEnd=thisStart=thisSum=0,maxSum=INT_MIN,j = 0; j < m; j++)  
    {  
      scanf("%d",&a[j]);  
      thisSum += a[j];  
  
      if(thisSum > maxSum)  
        {  
          maxSum = thisSum;  
          maxStart = thisStart;  
          maxEnd = j;  
        }  
      if(thisSum < 0)  
        {  
          thisSum = 0;  
          thisStart = j+1;  
        }  
    }  
      if(i > 1)  
    printf("\n");  
      printf("Case %d:\n",i);  
      printf("%d %d %d\n",maxSum,maxStart+1,maxEnd+1);  
    }  
  return 0;  
}

프로그램의 주요 부분은 여전히 ​​입니다. 위와 같이 알고리즘은 하위 시퀀스의 첫 번째 및 마지막 인덱스 번호 처리만 추가합니다.