Meximum Subarray Sum, использующий Divide-And-Conquer

Question

Работа над реализацией поиска Наибольшая смежная сумма последовательности с использованием метода Divide and Conquer, как видно here.

Мое возвращаемое значение часто неверно. Например:

{5, 3} returns 5 instead of 8. 
{-5, 3} returns 0 instead of 3. 
{ 6, -5, 7 } returns 7 instead of 8. 

Другие ноты:

• декрементирование или приращением AT первой или последней итераторы бросает исключение, сказав, что я либо не может увеличиваться, декремент или разыменования в этой точке. Я думаю, что в GCSMid есть ошибка, но я не смог ее решить.

• эта реализация использует итераторы произвольного доступа, означали, как RAIter

  //function max- finds greatest number given 3 size_ts 
  size_t max(size_t a, size_t b, size_t c) 
  { 
      if (a >= b && a >= c) 
      { 
       return a; 
      } 
  
      else if (b >= a && b >= c) 
      { 
       return b; 
      } 
      else 
      { 
       return c; 
      } 
  } 
  
  
      //function gcsMid 
      //main algorithm to find subsequence if it spans across the center line 
      template<typename RAIter> 
      size_t gcsMid(RAIter first, RAIter center, RAIter last) 
      { 
      size_t sum = 0; 
      size_t leftSum = 0; 
      size_t rightSum = 0; 
  
      //to the left of center 
      for (RAIter i = center; i > first; i--) 
      { 
       sum += *i; 
       if(sum > leftSum) 
       { 
        leftSum = sum; 
       } 
      } 
  
      //to right of center 
      sum = 0; 
      for (RAIter j = (center + 1); j < last; j++) 
      { 
       sum += *j; 
       if (sum > rightSum) 
       { 
        rightSum = sum; 
       } 
      } 
  
      //return the sums from mid 
      return leftSum + rightSum; 
  } 
  
  
  //main function to call 
  template<typename RAIter> 
  int gcs(RAIter first, RAIter last) 
  { 
      size_t size = distance(first, last); 
  
      //base case is when the subarray only has 1 element. when first == last 
      if (first == last || size == 1) 
      { 
       if (size < 1) 
       { 
        return 0; 
       } 
  
       if (*first < 0) 
       { 
        return 0; 
       } 
  
       return *first; 
      } 
  
      //middle point 
      RAIter center = first + (size/2); 
  
      //return max of leftsum, rightsum, and midsum 
      return max(gcs(first, center), 
         gcs(center + 1, last), 
         gcsMid(first, center, last));  
  } 
  

Answer 1

У вас есть две проблемы с кодом:

A. Эта петля:

for (RAIter i = center; i > first; i--) 

делает не включают first в цикл. Обратный алгоритм. Вы не можете просто использовать >= в качестве эталонного алгоритма, так как он не работает для итераторов. Либо добавьте дополнительный бит кода для проверки first в конце, либо измените свой цикл, чтобы он каким-то образом включал first (возможно, цикл while будет лучше подходит).

B. Эти определения:

size_t sum = 0; 
size_t leftSum = 0; 
size_t rightSum = 0; 

не должно быть size_t в size_t беззнаковым. Это означает, что когда сумма становится отрицательной, проверки, такие как if(sum > leftSum), больше не работают, так как отрицательное значение (которое меньше) больше положительного.

Измените их на int.

Лучший способ найти эти ошибки - запустить код через отладчик. Затем вы можете пройти через каждую строку своего кода и посмотреть, какие значения переменных. Это позволяет легко обнаруживать такие вещи, как отрицательные числа, которые становятся большими положительными числами, как указано выше.