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

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

Везде, где я смотрел онлайн, такие как это powerpoint показывает, что мой код должен работать. Я также видел нечто похожее на это, но в 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