0

here is recursive code for finding maximum subvector sum

#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;
}

it rerurns 155 while other non recursive method returns 187 please help

Improve this question
1
  • 1
    Basic debugging: although you've identified what you expect, and what you actually get, you haven't taken any steps to narrow the problem down. Trace through the program, either with printf, a debugger, or by hand, and you will see where it goes wrong. Commented Nov 22, 2010 at 18:51

4 Answers 4

Reset to default
5

@user466411: You have asked 274 questions in the last 7 months, or roughly a question every single day. Many of these questions have been [Closed], received serious negative votes [-5 or more], or both.

This pattern indicates clearly:
You need to re-think how you approach programming.

  • You need to learn to use a debugger.
  • You need to narrow down large problems to specific issues.
  • You need to precisely describe problems.
  • You need to test pieces of code before combining them into larger elements.
  • You need to attempt fixes, observe the effects, hypothesize solutions and test them.

All in all, you are programming wrong.
Most new programmers can master elementary programming in far less than 7 months without daily hand-holding. Either you need to approach programming anew, learning fresh how to think about code, or you need to acknowledge that programming is not for you, and you should find a new line of work.

(to other commenters: yes, I know this answer is non-responsive to this question, but it desperately needed to be said; see my other post for a responsive answer, trying to guide poster to a solution)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

thank you. You might add some SO specific advice like "don't create duplicate questions for the same issue" and "pay closer attention to code formatting".
1

Typo, this:

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

should be

rmax=std::max(rmax,sum1);
Improve this answer

Comments

1

Code I wrote and tested correct. Thought it might be useful...

#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;
}
Improve this answer

Comments

0

Where do you think the maximum subvector sum is, that generates the answer 187?
I believe it is the sequence: [59, 26, -53, 58, 97].

Which subvector sum generates your answer of 155?
I believe it is the sequence: [58, 97].

Why does your algorithm not pickup on the larger subvector sum?
Thats a darn good question. You can answer it yourself with basic debugging techniques.

At the end of the first call, your LMax should be 22, your RMax should be 123, and the TotalSum should be 145 (found by tracing the program by hand). Do you agree?

What does the 2nd call to maximum3 generate?

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.