给定n个整数组成的序列a1,a2,…an, 求子段和ai+ai+1+…+aj（子段可为空集）的最大值。
动态规划方程
b[j]=max(b[j-1]+a[j],a[j]) 1<=j<=n
最大子段和核心算法
1
2
3
4
5
6
7
8
9
10
11
|
int maxsum(int *a,int n)
{
int b=0,sum=0;
for(int i=1;i<=n;i++)
{
if(b>0)b+=a[i];
else b=a[i];
if(b>sum)sum=b;
}
return sum;
}
|
全部代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
using namespace std;
int Maxsum(int n,int *a)
{
int sum=0,b=0;
for(int i=1;i<=n;i++)
{
if(b>0)b+=a[i];
else b=a[i];
if(b>sum)sum=b;
}
return sum;
}
int main()
{
int m;
cin>>m;
for(int t=0;t<m;t++)
{
int *n=new int(m);
for(int j=0;j<m;j++)
{
cin>>n[j];
int *p=new int(n[j]);
for(int i=1;i<=n[j];i++)
cin>>p[i];
int t=Maxsum(n[j],p);
cout<<t<<endl;
}
}
}
|
近期评论