phoenix1.cpp

可以求最大子段和的优良代码,采用动态规划的方法求得,算法效率较高

#include "stdio.h"
int maxsum(int m,int n,int a[])
{
 if(n<m||m<1) return 0;
 int *b=new int [n+1];
 int *c=new int [n+1];
 b[0]=0;
 c[1]=0;
 for(int i=1;i<=m;i++)
 {
  b[i]=b[i-1]+a[i];
  c[i-1]=b[i];
  int max=b[i];
  for(int j=i+1;j<=i+n-m;j++)
  {
	  b[j]=b[j-1]>c[j-1]?b[j-1]+a[j]:c[j-1]+a[j];
      c[j-1]=max;
	  if(max<b[j]) max=b[j];
  }
  c[i+n-m]=max;
 }
 int sum=0;
 for(int j=m;j<=n;j++)
	 if(sum<b[j]) sum=b[j];
 return sum;
}
void main()
{
	int a[]={-2,11,-4,13,-5,-2};
	int max,m;	
	printf("请输入m:");
	scanf("%d",&m);
	max=maxsum(m,5,a);
	printf("最大子段和为%d\n",max);
}