动态规划-最小子段和

 #include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
void main()  { 
int i,j,k,t,n,s,smin,q[1000],a[1000];    
t=time(0)%1000;srand(t);          //  随机数发生器初始化     
printf("  序列中n个正负项,请确定n:");   
scanf("%d",&n);    
printf("  序列的%d个整数为：
  ",n);   
for(i=1;i<=n;i++)      {
t=rand()%(4*n)+10;            // 随机产生n个整数       
if(t%2==1) a[i]=-1*(t-1)/2;   // 把奇数变为负数，大小减半      
else a[i]=t/2;                // 把偶数大小减半      
printf("%d,",a[i]);      }    
smin=1000;q[0]=0;   
for(j=1;j<=n;j++)      {
if(q[j-1]>=0) q[j]=a[j];      
else q[j]=q[j-1]+a[j];       
if(q[j]<smin)         //比较得最小值        
{smin=q[j];k=j;} }  
printf("
  最小子段和为：%ld
",smin);  
for(s=0,i=k;i>=1;i--)    // 反推最小和子段的首标i    
{ s+=a[i]; 
if(s==smin) break; }  
printf("  最小子段从序列的第%d项到第%d项。
",i,k); }