Pagini recente » Cod sursa (job #1666651) | Cod sursa (job #1184748) | Cod sursa (job #4286) | Cod sursa (job #1081046) | Cod sursa (job #955809)
Cod sursa(job #955809)
#include <fstream>
#include <tuple>
std::tuple< int, int, int > max_subarray( const short* const p, const int size, const int k )
{
int sum_max = -25001;
int begin = 0, end = 0;
int sum = 0;
for ( int i = 0; i < size; i++ )
{
sum += p[ i ];
if ( sum < 0 )
{
sum = 0;
begin = i;
if ( p[ i ] >= sum_max )
{
sum_max = p[ i ];
begin = end = 1;
}
}
else
{
if ( sum >= sum_max || end - begin + 1 < k )
{
sum_max = sum;
end = i;
}
}
}
return std::make_tuple( begin, end, sum_max );
}
int main()
{
std::ifstream cin("secv2.in");
std::ofstream cout("secv2.out");
int n = 0, k = 0;
cin >> n >> k;
short num[ 50000 ];
int sum = 0;
for ( int i = 0; i < n; i++ )
cin >> num[ i ], sum += num[ i ];
auto ans = max_subarray( num, n, k );
int begin = std::get< 0 >( ans );
int end = std::get< 1 >( ans );
int sum_max = std::get< 2 >( ans );
if ( n == k )
cout << 1 << " " << n << " " << sum;
else
cout << begin + 1 << " " << end + 1 << " " << sum_max;
}