サブストリング和
1554 ワード
サブストリング和
時間制限:
5000 ms|メモリ制限:
65535 KB
難易度:
3
説明
整数数列{a 1,a 2...,an}が与えられ、1<=x<=y<=nのサブシーケンスの和が最大になるように、連続非空サブ列{ax,ax+1,...,ay}が見出される.
入力
1行目は整数N(N<=10)であり、テストデータのグループ数を表す.
各試験データの最初の行は、整数nがシーケンスにn個の整数を表し、その後の行にはn個の整数I(−100=しゅつりょく
各テストデータの出力と最大の連続サブ列の和.
サンプル入力
サンプル出力
ヒント
入力データが多いのでscanfでの入力をおすすめします
マイコード:
スレッド:
時間制限:
5000 ms|メモリ制限:
65535 KB
難易度:
3
説明
整数数列{a 1,a 2...,an}が与えられ、1<=x<=y<=nのサブシーケンスの和が最大になるように、連続非空サブ列{ax,ax+1,...,ay}が見出される.
入力
1行目は整数N(N<=10)であり、テストデータのグループ数を表す.
各試験データの最初の行は、整数nがシーケンスにn個の整数を表し、その後の行にはn個の整数I(−100=
各テストデータの出力と最大の連続サブ列の和.
サンプル入力
1
5
1 2 -1 3 -2
サンプル出力
5ヒント
入力データが多いのでscanfでの入力をおすすめします
マイコード:
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
int N,n,i,j;
int dp[1000010],a[1000010];
scanf("%d",&N);
while (N--)
{
scanf("%d",&n);
for (i=0;i<n;++i)
{
scanf("%d",&a[i]);
}
dp[0]=a[0];
for (i=1;i<n;++i)
{
if (dp[i-1]+a[i]>=0&&dp[i-1]>0)
{
dp[i]=dp[i-1]+a[i];
}
else
{
dp[i]=a[i];
}
}
j=dp[0];
for (i=1;i<n;++i)
{
if (j<dp[i])
{
j=dp[i];
}
}
printf("%d
",j);
}
return 0;
}スレッド:
#include<stdio.h>
int main()
{
int n,m,i,max,sum;
scanf("%d",&n);
while(n--)
{
max=0;
scanf("%d",&m);
scanf("%d",&sum);
max=sum;
while(--m)
{
scanf("%d",&i);
if(sum<0) sum=i;
else sum+=i;
if(sum>max) max=sum;
}
printf("%d
",max);
}
}