fork download
copy 
  1. #include <iostream>
  2. #include <iterator>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <utility>
  6.  
  7. int MaxSum(int lo, int hi, const int* arr)
  8. {
  9.     if (lo > hi)
  10.     {
  11.         return 0;
  12.     }
  13.     if (lo == hi)
  14.     {
  15.         return arr[lo];
  16.     }
  17.  
  18.     int mid = (lo + hi) / 2;
  19.  
  20.     int maxLeft = 0;
  21.     int maxRight = 0;
  22.  
  23.     int sum = 0;
  24.  
  25.     for (int i = mid; i >= lo; --i)
  26.     {
  27.         sum += arr[i];
  28.         if (sum > maxLeft)
  29.         {
  30.             maxLeft = sum;
  31.         }
  32.     }
  33.  
  34.     sum = 0;
  35.     for (int i = mid + 1; i <= hi; ++i)
  36.     {
  37.         sum += arr[i];
  38.         if (sum > maxRight)
  39.         {
  40.             maxRight = sum;
  41.         }
  42.     }
  43.  
  44.     int MaxCrossing = maxLeft + maxRight;
  45.  
  46.     int maxInA = MaxSum(0, mid, arr);
  47.     int maxInB = MaxSum(mid + 1, hi, arr);
  48.  
  49.     return std::max(MaxCrossing, std::max(maxInA, maxInB));
  50. }
  51.  
  52. void test(const std::pair<std::vector<int>, int> & seq)
  53. {
  54.     int result = MaxSum(0, seq.first.size() - 1, seq.first.data());
  55.     std::cout << "Expected " << seq.second << ", got " << result << '\n';
  56. }
  57.  
  58. int main()
  59. {
  60.     std::vector<std::pair<std::vector<int>, int>> sequences =
  61.     {
  62.         { { -10, 11, 10, -10, 2, 3, -6, 1 }, 21 },
  63.         { { -10, 11, 10, -3, 8, 3, 4, -6, 1 }, 33 },
  64.     };
  65.  
  66.     for (auto& sequence : sequences)
  67.         test(sequence);
  68. }
Success #stdin #stdout 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Expected 21, got 21
Expected 33, got 33
https://ideone.com/9T1MPi
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!