рекурсивный метод нахождения максимального субвектора

Question

вот рекурсивный код для поиска максимальной суммы субвекторов

#include <iostream>
using namespace std;

int Max(int a,int b,int c){
    return max(a,std::max(b,c));
}
int a[]={31,-41,59,26,-53,58,97,-93,-23,84};
int n=sizeof(a)/sizeof(int);
int maximum3(int l,int u){
    if (l>u) return 0;
    if (l==u) return std::max(0,a[l]);

    int m=(l+u)/2;
    int lmax=0;
    int sum=0;
    int rmax=0;
    int sum1=0;
    for (int i=m;i>=l;i--){
        sum+=a[i];
        lmax=std::max(lmax,sum);
    }
    for (int j=m+1;j<u;j++){
        sum1+=a[j];
        rmax=std::max(rmax,sum);
    }

    return Max(lmax+rmax,maximum3(l,m),maximum3(m+1,u));
}

int main(){
    cout<<maximum3(0,n-1)<<"  ";
    return 0;
}

он возвращает 155, тогда как другой нерекурсивный метод возвращает 187, помогите

Answer 1

@ user466411 : Вы задали 274 вопросов за последние 7 месяцев или примерно вопрос каждый день. Многие из этих вопросов были [закрыт] , получили серьезные отрицательные голоса [- 5 или более] или оба.

Эта схема четко указывает на:
Вам нужно переосмыслить подход к программированию .

• Вам нужно научиться пользоваться отладчиком.
  
• Вам необходимо сузить большие проблемы до конкретных проблем.
  
• Вам нужно точно описать проблемы.
  
• Вам нужно протестировать куски кода перед объединением их в более крупные элементы.
  
• Вам нужно попытаться исправить, наблюдать за эффектами, выдвигать гипотезы решений и проверять их.
  

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

(другим комментаторам: да, я знаю, что этот ответ не отвечает на этот вопрос, но его отчаянно нужно было сказать; см. Мой другой пост для ответного ответа, пытающегося направить плакат к решению)

Answer 2

Код, который я написал и протестировал правильно.Думал, что это может быть полезно ...

#include <iostream.h>

void findMaxCrossSubArray(int a[], int low, int mid, int high, int crossCur[])
{
    int leftSum = -9999;
    int sum = 0;
    int maxLeft, maxRite;

    maxLeft = maxRite = 0;

    for (int i = mid; i >=  low; i--)
    {
        sum += a[i];
    if (sum > leftSum)
    {
        leftSum = sum;
        maxLeft = i;
    }
    }
    int riteSum = -9999;
    sum = 0;
    for (int j = mid + 1; j <= high; j++)
    {
        sum += a[j];
        if (sum > riteSum)
    {
        riteSum = sum;
        maxRite = j;
    }
    }
    crossCur[0] = maxLeft;
    crossCur[1] = maxRite;
    crossCur[2] = leftSum + riteSum;
    return;
} 

void findMaxSubArray (int a[], int low, int high, int curMax[])
{
    if (high == low)
    {
        curMax[0] = low;
    curMax[1] = high;
    curMax[2] = a[low];
    return;
    }

    int mid = (low + high)/2;

    int leftCur[3], riteCur[3], crossCur[3];
    findMaxSubArray(a, low, mid, leftCur);
    findMaxSubArray(a, mid+1, high, riteCur);
    findMaxCrossSubArray(a, low, mid, high, crossCur);

    if ((leftCur[2] >= riteCur[2]) && (leftCur[2] >= crossCur[2]))
    {
        curMax[0] = leftCur[0];
    curMax[1] = leftCur[1];
    curMax[2] = leftCur[2];
    return;
    }
    if ((riteCur[2] >= leftCur[2]) && (riteCur[2] >= crossCur[2]))
    {
        curMax[0] = riteCur[0];
    curMax[1] = riteCur[1];
    curMax[2] = riteCur[2];
    return;
    }

    curMax[0] = crossCur[0];
    curMax[1] = crossCur[1];
    curMax[2] = crossCur[2];
    return;
}   

int main()
{
    int a[] = {13, -3, -25, 20, -3, -16, -23, 18, 20,-7, 12, -5, -22, 15, -4, 7};
    int curMax[] = {0,0,0};

    findMaxSubArray(a, 0, 15, curMax);

    cout << curMax[0] << "," << curMax[1] << "," << curMax[2] << endl;
}    

Answer 3

Опечатка, это:

rmax=std::max(rmax,sum); 

должно быть

rmax=std::max(rmax,sum1);

Answer 4

Как вы думаете, где максимальная сумма субвектора, которая генерирует ответ 187?
Я полагаю, что это последовательность: [59, 26, -53, 58, 97].

Какая сумма подвекторов генерирует ваш ответ 155?
Я полагаю, что это последовательность: [58, 97].

Почему ваш алгоритм не улавливает большую сумму подвекторов?
Это чертовски хороший вопрос.Вы можете ответить на него сами с помощью основных методов отладки.

В конце первого вызова ваш LMax должен быть 22, ваш RMax должен быть 123, а TotalSum должен быть 145 (найдено путем отслеживания программы вручную) .Ты согласен?

Что генерирует 2-й звонок к Maximum3?