问题描述:给定整型数组a[n](n>0),要求数组a[n]中相邻元素的最小和.
例如:1 -2 3 -1 -5 -4 1 0 -2 5 -1
则a中相邻元素的最小和为(-1)+(-5)+(-4)+1+0+(-2)=-11.

问题要求:求一时间复杂度为O(n)算法.谢谢!

[此贴子已经被作者于2006-9-17 23:04:48编辑过]

应该是最小子段和吧.
设f[i]为第i个元素为最后一个元素的最小和,
若f[i-1]>0,f[i]=a[i];
若f[i-1]<0,f[i]=a[i]+f[i-1];
f[0]=0;
一个for循环就可以搞定了

/*是这样吗?太感谢你了,谢谢...*/
#include<stdio.h>
#define N 50
int Min(int a[],int n)
{
int i=1,min=0,f[N];
f[0]=a[0];
min=f[0];
while(i<n)
{
if(f[i-1]>0)
{
f[i]=a[i];
}
else
{
f[i]=a[i]+f[i-1];
}
if(f[i]<min)
{
min=f[i];
}
//printf("%d\n",f[i]);
i++;
}
return(min);
}

int main()
{
int a[N]={1,-2,3,-1,-5,-4,1,0,-2,5,-1};
printf("min=%d\n",Min(a,11));
return(0);
}

恩,差不多是这样子,
事实上数组f用一个变量代替就足够了

后来想到了．

#include<stdio.h>
#define N 50
int Min(int a[],int n)
{
int i=1,min=0,f;
f=a[0];
min=f;
while(i<n)
{
if(f>0)
{
f=a[i];
}
else
{
f=a[i]+f;
}
if(f<min)
{
min=f;
}
//printf("%d\n",f);
i++;
}
return(min);
}

int main()
{
int a[N]={1,-2,3,-1,-5,-4,1,0,-2,5,-1};
printf("min=%d\n",Min(a,11));
return(0);
}

对于 -1,4,1,3,-1
调用Min(a,5)
输出-1,相邻元素的最小和应该是 3+(-1)=2
1,2,3,4,5 调用Min(a,5) 输出的是1
应该是1+2=3啊

[1,1]也算一个区间的.

问题描述:给定整型数组a[n](n>0),要求数组a[n]中相邻元素的最小和.
例如:1 -2 3 -1 -5 -4 1 0 -2 5 -1
则a中相邻元素的最小和为(-1)+(-5)+(-4)+1+0+(-2)=-11.

一个数也是相邻吗？


#include<stdio.h>
#define N 50
int Min(int a[],int n)
{
int i=1,min=0,f;
f=a[0];
min=a[0]+a[1];
while(i<n)
{
if(f>0)
{
f=a[i]+a[i-1];
}
else
{
f=a[i]+f;
}
if(f<min)
{
min=f;
}
//printf("%d\n",f);
i++;
}
return(min);
}

int main()
{
int a[N]={1,-2,3,-1,-5,-4,1,0,-2,5,-1};
printf("min=%d\n",Min(a,11));
return(0);
}

个人的理解不同而已........