目录
题目描述
给定n个整数(可能是负数)组成的序列a[1], a[2], a[3], …, a[n],求该序列的子段和如a[i]+a[i+1]+…+a[j]的最大值。
输入
每组输入包括两行,第一行为序列长度n,第二行为序列。
输出
输出字段和的最大值。
样例输入输出
样例输入
5
-1 0 1 2 3
样例输出
6
两种解决方法
第一种dp
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,i,a[100],max1,b[100];
while(~scanf("%d",&n))
{
for(i=0; i<n; i++)
scanf("%d",&a[i]);
b[0]=a[0];
max1=b[0];
// b[i]表示以a[i]结尾的最大子段和
for(i=1; i<n; i++)
{
if(b[i-1]>0)
b[i]=b[i-1]+a[i];
else
b[i]=a[i];
if(b[i]>max1)
max1=b[i];
}
printf("%d\n",max1);
}
}
第二种
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T,n,a[100005];
while(~scanf("%d",&n))
{
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
int temp=0;
// temp表示temp对应位置的之前的最大子段和
int max1=a[0];
for(int i=0; i<n; i++)
{
temp+=a[i];
if(temp>=max1)
{
max1=temp;
}
if(temp<0)
{
temp=0;
}
}
// temp用来累加a[i],当temp<0 令temp=0,从当前位置继续累加,
//若temp>0 表示在temp对于i之前的最大子段和大于0
printf("%d\n",max1);
}
}