Cod sursa(job #1527935)
| Utilizator | Data | 18 noiembrie 2015 21:18:24 | |
|---|---|---|---|
| Problema | Subsecventa de suma maxima | Scor | 95 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.62 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("ssm.in");
ofstream fout("ssm.out");
int DP[6000005],v[6000005];
int n,Max,j;
void read()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i];
}
}
void f()
{
DP[1]=v[1];
Max=DP[1];
for(int i=2;i<=n;i++)
{DP[i]=max(DP[i-1]+v[i],v[i]);
if(Max<DP[i])
{
j=i;
Max=DP[i];
}
}
}
int main()
{
int k;
read();
f();
k=j;
fout<<Max<<" ";
while(Max!=0)
{
Max=Max-v[k];
k--;
}
fout<<k+1<<" "<<j;
}
