fork(2) download
copy 
  1. #include <algorithm>
  2. #include <iterator>
  3. #include <iostream>
  4. #include <numeric>
  5. #include <ostream>
  6. #include <utility>
  7. #include <vector>
  8.  
  9. // __________________________________________________
  10.  
  11. template<typename RandomAccessIterator> typename std::iterator_traits<RandomAccessIterator>::value_type
  12. max_subarr_k(RandomAccessIterator first,RandomAccessIterator last,int k)
  13. {
  14.     using namespace std;
  15.     typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
  16.     if(distance(first,last) < k)
  17.         return value_type(0);
  18.     RandomAccessIterator tail=first;
  19.     first+=k;
  20.     value_type window=accumulate(tail,first,value_type(0));
  21.     value_type max_sum=window, current_sum=window;
  22.     while(first!=last)
  23.     {
  24.         window += (*first)-(*tail) ;
  25.         current_sum = max( current_sum+(*first), window );
  26.         max_sum = max(max_sum,current_sum);
  27.         ++first;
  28.         ++tail;
  29.     }
  30.     return max_sum;
  31. }
  32.  
  33. // __________________________________________________
  34.  
  35. template<typename E,int N>
  36. E *end(E (&arr)[N])
  37. {
  38.     return arr+N;
  39. }
  40.  
  41. int main()
  42. {
  43.     using namespace std;
  44.     int arr[]={1,2,4,-5,-4,-3,2,1,5,6,-20,1,1,1,1,1};
  45.     cout << max_subarr_k(arr,end(arr),4) << endl;
  46.     cout << max_subarr_k(arr,end(arr),5) << endl;
  47. }
  48.  
Success #stdin #stdout 0.01s 2680KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14
11
https://ideone.com/Sd2JTu
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!