|
给出了常规思路、改进思路、分治法、动态规划等四种算法。
#include <stdio.h>
//最大子段和 常规思路
int maxSubSum1()
{
int n;
int *a;
int i,j,k,sum=0,thissum, besti, bestj;
printf("input the total number of all integers:");
scanf("%d",&n);
a=new int[n];
for(i=0;i<n;i++)
scanf("%d",a+i);
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)
{
thissum=0;
for(k=i;k<=j;k++)
{
thissum+=a[k];
}
if (thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
printf("from %d to %d, result is %d\n",besti,bestj, sum);
return 0;
}
//最大子段和，改进算法
int maxSubSum2()
{
int n;
int *a;
int i,j,k,sum=0,thissum, besti, bestj;
printf("input the total number of all integers:");
scanf("%d",&n);
a=new int[n];
for(i=0;i<n;i++)
scanf("%d",a+i);
for(i=0;i<n;i++)
{
thissum=0;
for(j=i;j<n;j++)
{
thissum+=a[j];
if (thissum>sum)
{
sum=thissum;
besti=i;
bestj=j;
}
}
}
printf("from %d to %d, result is %d\n",besti,bestj, sum);
return 0;
}
//分治法
int maxSubSum3(int *a, int left, int right)
{
int sum=0;
int center;
int i;
int leftSum, rightSum, s1,s2,lefts,rights;
if(left==right)
sum=a[left]>0?a[left]:0;
else{
center=(left+right)/2;
leftSum=maxSubSum3(a,left,center);
rightSum=maxSubSum3(a,center+1,right);
lefts=0;s1=0;
for(i=center;i>=left;i--)
{
lefts=lefts+a[i];
if(lefts>s1)
s1=lefts;
}
rights=0;s2=0;
for(i=center+1;i<=right;i++)
{
rights=rights+a[i];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if (sum<leftSum)
sum=leftSum;
if (sum<rightSum)
sum=rightSum;
}
return sum;
}
//动态规划算法
int maxSubSum4(int n, int *a)
{
int sum=0,b=0;
int i;
for(i=0;i<n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum)
sum=b;
}
return sum;
}
int main()
{
int n;
int *a;
int i,j,k,sum=0,thissum, besti, bestj;
printf("input the total number of all integers:");
scanf("%d",&n);
a=new int[n];
for(i=0;i<n;i++)
scanf("%d",a+i);
//maxSubSum1 //常规思路
//maxSubSum2 //改进思路
//printf("%d\n",maxSubSum3(a,0,n-1)); //分治策略
printf("%d\n",maxSubSum4(n,a));<span style="white-space:pre"> </span>//动态规划
return 0;
}
| 
转播
