欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

最大连续子序列和问题

程序员文章站 2022-04-10 10:38:18
...
问题描述:给定一个序列a[1],a[2]...a[n],求解其连续子序列中元素和的最大值
例如: 6 -1 5 4 -7 这个序列最大连续子序列和为14
具体问题见: HDOJ 1003 TZU 1202
这个问题在《数据结构与算法分析--c语言描述》(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;  
}


程序主要部分还是上面的算法,只是加上了对子序列首尾索引号的处理。