Mai intai trebuie sa te autentifici.
Cod sursa(job #1568898)
| Utilizator | Data | 14 ianuarie 2016 20:08:53 | |
|---|---|---|---|
| Problema | Subsecventa de suma maxima | Scor | 10 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.85 kb |
#include <fstream>
using namespace std;
ifstream fin("ssm.in");
ofstream fout("ssm.out");
int N,v[1000],Smax,a,b;
struct A{
int suma,prim,ultim;
}Dp[1000];
void citire()
{
fin>>N;
for(int i=1;i<=N;i++)
fin>>v[i];
}
void rezolvare()
{
Dp[1].suma=v[1];
Dp[1].prim=1;
Dp[1].ultim=1;
for(int i=2;i<=N;i++)
{
if(Dp[i-1].suma>=0)
{
Dp[i].suma=Dp[i-1].suma+v[i];
Dp[i].prim=Dp[i-1].prim;
Dp[i].ultim=i;
}
else
{
Dp[i].suma=v[i];
Dp[i].prim=i;
Dp[i].ultim=i;
}
}
}
void afisare()
{
Smax=-2000000;
for(int i=1;i<=N;i++)
{
if(Smax<=Dp[i].suma)
Smax=Dp[i].suma;
a=Dp[i].prim;
b=Dp[i].ultim;
}
fout<<Smax<<" "<<a<<" "<<b;
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}
