最大子段和问题
#include<stdio.h>
int main()
{
int a[10]={31,-41,59,26,-53,58,97,-93,-23,84};
int b[10];
/*int i,j,k,sum;
int maxsofar=0;
for(i=0;i<10;i++)
{
for(j=i;j<10;j++)
{
sum=0;
for(k=i;k<j;k++)
{
sum+=a[k];
}
if(sum>maxsofar)
maxsofar=sum;
}
}
printf("%d\n",maxsofar);
}*/
动态规划法：
- 令b[j]表示以位置 j 为终点的所有子区间中和最大的一个
- 子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中
- 如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含
- 如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大
intmax = 0;
intb[n+1];
intstart = 0;
intend = 0;
memset(b,0,n+1);
for(inti = 1; i <= n; ++i)
{
if(b[i-1]>0)
{
b[i] = b[i-1]+a[i];
}else{
b[i] = a[i];
}
if(b[i]>max)
max = b[i];
}
优质内容筛选与推荐>>1、Nginx+uWSGI+Django原理
2、多种方式读取GridView某行的值
3、alipay特殊字符未过滤问题
4、机器学习 斯坦福大学公开课（1）
5、TCP-IP协议简介