給定n個整數（可能為負數）組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。當所給的整均為負數時定義子段和為0。要求算法的時間復雜度為O(n)。輸入格式:輸入有兩行： 第一行是n值（1<=n<=10000)； 第二行是n個整數。輸出格式:輸出最大子段和。輸入樣例:在這里給出一組輸入。例如：6-2 11 -4 13 -5 -2輸出樣例:在這里給出相應的輸出。例如：20#includeusing namespace std ; ………………………………………………
2 回答
倚天杖
TA貢獻1828條經驗 獲得超3個贊
也可以用DP
#include <stdlib.h>
#include<stdio.h>
int main()
{
int count;
int a[100];
int b[100];
int i;
int max;
scanf("%d",&count);
for(i=0; i<count; i++)
{
scanf("%d",&a[i]);
}
b[0]=a[0];
max=b[0];
for(i=1; i<count; 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];
}
printf("%d\n",max);
return 0;
}
嗶嗶one
TA貢獻1854條經驗 獲得超8個贊
#include <cstdio>
typedef long long LL;
int main(int argc, char const *argv[])
{
int n;
scanf("%d", &n);
LL t, tmp;
LL ans = 0;
for(int i = 0; i < n; i++)
{
scanf("%lld", &t);
if(i > 0 && tmp > 0)
t += tmp;
if(ans < t)
ans = t;
tmp = t;
}
printf("%lld\n", ans);
return 0;
}- 2 回答
- 0 關注
- 942 瀏覽
添加回答
舉報
0/150
提交
取消