Pagini recente » Cod sursa (job #2589316) | Cod sursa (job #538321) | Cod sursa (job #3156723) | Cod sursa (job #919227) | Cod sursa (job #2228132)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");
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.
long long vector_length, length_min, v[50001], sums[50001], min_sums[50001];
cin >> vector_length >> length_min;
sums[0] = 0;
min_sums[0] = 0;
for( int i=1 ; i<=vector_length ; i++ )
{
cin >> v[i];
sums[i] = sums[i-1] + v[i];
if( sums[i] > sums[min_sums[i-1]] )
min_sums[i] = min_sums[i-1];
else
min_sums[i] = i;
}
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;
}
}
cout << left << " " << right << " " << value;
return 0;
}