Pagini recente » Cod sursa (job #2938084) | Cod sursa (job #1235722) | Cod sursa (job #138396) | Cod sursa (job #684562) | Cod sursa (job #2228158)
#include <fstream>
using namespace std;
int main()
{
// sums[i] = suma elementelor v[0], v[1], v[2], ... v[i]
// suma elementelor v[i], v[i+1], v[i+2], ... v[j] = sums[j] - sums[i-1]
// min_sums[i] = pozitia minimului elementelor sums[0], sums[1], sums[2], ... sums[i]
// Folosind min_sums vom puteam gasi secventa de suma maxima care se termina pe pozitia i
// de orice lungime. Suma secventei este sums[i] - sums[min_sums[i-lungime-1]],
// incepe la min_sums[i-lungime-1]+1 si se termina la i.
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int long long vector_length, length_min, number, sums[50001], min_sums[50001];
fin >> vector_length >> length_min;
sums[0] = 0;
min_sums[0] = 0;
for( int i=1 ; i<=vector_length ; i++ )
{
fin >> number;
sums[i] = sums[i-1] + number;
if( sums[i] > sums[min_sums[i-1]] )
min_sums[i] = min_sums[i-1];
else
min_sums[i] = i;
}
int long long left, right, value = LONG_LONG_MIN;
for( int i=length_min ; i<=vector_length ; i++ )
{
if( value < sums[i] - sums[min_sums[i-length_min-1]] )
{
value = sums[i] - sums[min_sums[i-length_min-1]];
left = min_sums[i-length_min-1]+1;
right = i;
}
}
fout << left << " " << right << " " << value;
fin.close();
fout.close();
return 0;
}