Разделяй и властвуй - покупай или продавай? (Максимальный последовательный подмассив)

Суть программы заключается в том, чтобы найти максимальный подмассив одномерного массива с колеблющимися ценами на акции, используя как метод грубой силы (который работает!), так и метод «разделяй и властвуй» (который не работает). Цель программы — найти набор дней (отсюда lsub и rsub в структуре) и максимальную прибыль за эти дни.

Везде, где я искал в Интернете, например, " Я тоже видел нечто подобное, но в Java на StackOverflow реализация того кода тоже не работает. Вот ссылка на эту программу Java.

Мой код выглядит следующим образом:

#include <stdio.h>
#include <iostream>
#include <climits>
#include <cstring>

struct funOut{
int lsub; //Left subscript
int rsub; //Right subscript
int maximum; //Contains the max value
 //This way, max has the absolute smallest value and only needs to be done once rather than at the beginning of the algorithm calls.
};

void load(int arr[], int n);
void brute(int arr[],  int n, funOut &out);
funOut dac(int arr[], int low, int high, funOut &out);
void findMax(int sumLval, int sumRval, funOut &sumMval, int low, int mid, int high, funOut &out);
funOut crossSum(int arr[], int low, int mid, int high);
void print(funOut out);

using namespace std;


int main(void)
{
   funOut out;

   string alg;
   cin >> alg;

   int n;
   cin >> n;

   int arr[n];

   // cout << n << endl;

   load(arr, n);
   if(alg[0] == 'b')
      brute(arr, n, out); //PARAMETERS NEEDED
   else if(alg[0] == 'd')
   {
      out.maximum = 0;
      out = dac(arr, 1, n-1, out);
   }

   else
   {
      cout << "\nERROR: No algorithm chosen, aborting program." << endl;
      return 0;
   }

   cout << "Before Print" << endl;
   print(out);
   return 0;
}

void load(int arr[], int n)
{
   cout << "Loading" << endl;
   for(int i=0; i<n; i++)
      cin >> arr[i];
}

void brute(int arr[], int n, funOut &out) //THIS WORKS!!!
{
   out.maximum = 0;
   int change;
   int temp = 0;
   for(int i=1; i<n-1; i++)
   {
      for(int j=i; j<n; j++)
      {
         change = arr[j] - arr[j-1];
         temp += change;
         if(temp > out.maximum){
            out.lsub = i;
            out.rsub = j;
            out.maximum = temp;
         }     
      }
      temp = 0;
   }
}

funOut dac(int arr[], int low, int high, funOut &out)
{
   cout << "DAC Start!" << endl;
   if(low == high)
   {
      out.lsub = out.rsub = low;
      out.maximum = arr[low];
      return out;
   }
   else
   {
      // cout << "DAC IF" << endl;
      int mid = (low + high)/2;

      funOut sumLval = dac(arr, low, mid, out);
      funOut sumRval = dac(arr, mid+1,high, out);
      funOut sumMval = crossSum(arr, low, mid, high);

      cout << "\nsumLval = " << sumLval.maximum << endl; 
      cout << "\nsumRval = " << sumRval.maximum << endl;
      cout << "\nsumMval = " << sumMval.maximum << endl;
      //FindMax
      if(sumLval.maximum >= sumRval.maximum && sumLval.maximum >= sumMval.maximum)
         return sumLval;         
      else if(sumRval.maximum >= sumLval.maximum && sumRval.maximum >= sumMval.maximum)
         return sumRval;
      else
         return sumMval;
   }
}



funOut crossSum(int arr[], int low, int mid, int high)
{
funOut sumMval;
int lsum = 0;
int rsum = 0;
int sum = 0;
int maxl, maxr;
//For loop finding lsum
for(int i=mid; i>=low; i--)
{
   cout << "DAC For I = " << i << endl;
   sum += arr[i];
   if(sum > lsum)
   {
      lsum = sum;
      maxl = i;
   }
}

sum = 0;

for(int j=mid+1; j<=high; j++)
{
   cout << "DAC For J = "<< j << endl;
   sum += arr[j];
   if(sum > rsum)
   {
      rsum = sum;
      maxr = j;
   }
}

sumMval.lsub = maxl;
sumMval.rsub = maxr;
sumMval.maximum = lsum + rsum;

return sumMval;
}

void print(funOut out)
{
   cout << "The max value is: ";
   cout << out.maximum << endl;
   cout << "The left subscript is: ";
   cout << out.lsub << endl;
   cout << "The right subscript is: ";
   cout << out.rsub << endl;
}

Пример набора данных: (Они должны быть на отдельных строках, но это не позволяет мне сделать это.)

d
17
100
113
110
85
105
102
86
63
81
101
94
106
101
79
94
90
97

Предполагаемый результат:

Максимальное значение: 43

Левый нижний индекс: 8

Правый нижний индекс: 11