Function call leads to no output

Question

This is my first time posting here, I'm new to c++ and was trying to implement maximum subarray problem

Problem: When the function max_subarray is called, it never returns resulting in no output

What I have Tried: I have narrowed the problem down to cross_max_subarray function because when I remove the function call from the max_subarray function OR comment out all the code from cross_max_subarray, the output is printed normally

What I want to know: A hint or an answer about what is the problem in the code would be nice and I'm also confused about if I try to print anything at the first line of the function.. it still gives no output.. wouldn't it be able to execute that print command?

I hope I did a good job in asking the question properly, Here is my code below:

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector<int> cross_max_subarray(vector<int> v,int low,int high,int mid){
    int lt_sum = -20000;
    int sum = 0;
    int lt_index = mid;
    for(int i = mid; i>=low; i--){
        sum += v[i];
        if(sum > lt_sum){
            i = lt_index;
            sum = lt_sum;
        }
    }
    int rt_sum = -20000;
    sum = 0;
    int rt_index = mid;
    for(int i = mid; i<=high; i++){
        sum += v[i];
        if(sum > rt_sum){
            i = rt_index;
            sum = rt_sum;
        }
    }
    std::vector<int> a = {lt_index, rt_index, lt_sum+rt_sum};
    return a;
}

vector<int> max_subarray(vector<int> v,int low,int high){
    cout << "gkjreor";
    if(low == high){
        std::vector<int> a = {low, high, a[low]};
        return a; 
    }
    int mid = (low+high)/2;
    vector<int> ll_lh_ls = max_subarray(v, low, mid);
    vector<int> rl_rh_rs = max_subarray(v, mid+1, high);
    vector<int> cl_ch_cs = cross_max_subarray(v, low, high, mid);

    int ls = ll_lh_ls[2];
    int rs = rl_rh_rs[2];
    int cs = cl_ch_cs[2];

    if(ls>=rs && ls>=cs){
        std::vector<int> a = {ll_lh_ls[0], ll_lh_ls[1], ls};
        return a;
    } else if(rs>=ls && rs>=cs){
        std::vector<int> a = {rl_rh_rs[0], rl_rh_rs[1], rs};
        return a;
    } else{
        std::vector<int> a = {cl_ch_cs[0], cl_ch_cs[1], cs};
        return a; 
    }
}

int main(){
    //number of elements
    int n;
    cin >> n;

    std::vector<int> v(n);
    // taking input
    for(int i = 0; i<n; i++){
        cin >> v[i];
    }

    // test print
    for(int i = 0; i<n; i++){
        cout << v[i] << " ";
    }
    // tried to flush output buffer
    cout << endl;

    // this is the function call that does not exit
    std::vector<int> l_h_s = max_subarray(v, 0, n-1);

    cout << l_h_s[2] << "\n";
    return 0;
}

Answer 1

There were a few errors that combined to make it a bit harder to debug your program. A quick tip is to try to build your code in as many small pieces as you can and test each one as you are making it. This helps you find problems early on.

The first issue that I had to change was that I had a problem with assigning the vectors with {}. For some reason my compiler didn't like it. If you didn't run into this issue then ignore this. I also noticed that you were using the std::vector despite the fact that you declared using namespace std at the top so I fixed that by removing std:: in front of all of the vectors.

The second major problem that I ran into was within cross_max_subarray. The problem was that you were assigning variables in the wrong direction. i = lt_index makes it so that you are always changing i and not lt_index like you were intending. This probably led to an infinite loop as i was constantly being = to mid every loop. While I was in that function I noticed that you were summing the mid number in both summations so it ended up adding it twice. To fix this I made the right side start at mid+1.

Another issue that I noticed was that you were esentually assigning a[2] = a[low]. This is an issue because a hasn't been filled with anything yet so a[low] is just garbage data. I'm pretty sure that you were just looking to do a[2] = v[low] because v is the vector that is actually holding the data.

All your mistakes seemed pretty easy to do and I fall victim to them pretty often. C++ can be quite confusing sometimes but try to not get discouraged.

This is the working code:

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector<int> cross_max_subarray(vector<int> v,int low,int high,int mid){
    int lt_sum = -20000;
    int sum = 0;
    int lt_index = mid;
    for(int i = mid; i>=low; i--){
        sum += v[i];
        if(sum > lt_sum){
            lt_index = i;
            lt_sum = sum;
        }
    }

    int rt_sum = -20000;
    sum = 0;
    int rt_index = mid;
    for(int i = mid+1; i<=high; i++){
        sum += v[i];
        if(sum > rt_sum){
            rt_index = i;
            rt_sum = sum;
        }
    }
    vector<int> a(3);
    a[0]= lt_index;
    a[1]= rt_index;
    a[2]= lt_sum+rt_sum;
    return a;
}

vector<int> max_subarray(vector<int> v,int low,int high){
//    cout << "gkjreor";
    vector<int> a(3);
    if(low == high){
        a[0]= low;
        a[1]= high;
        a[2]= v[low];
        return a; 
    }
    int mid = (low+high)/2;
    vector<int> ll_lh_ls = max_subarray(v, low, mid);
    vector<int> rl_rh_rs = max_subarray(v, mid+1, high);
    vector<int> cl_ch_cs = cross_max_subarray(v, low, high, mid);

    int ls = ll_lh_ls[2];
    int rs = rl_rh_rs[2];
    int cs = cl_ch_cs[2];

    if(ls>=rs && ls>=cs){
        a[0]= ll_lh_ls[0];
        a[1]= ll_lh_ls[1];
        a[2]= ls;
    } else if(rs>=ls && rs>=cs){
        a[0]= rl_rh_rs[0];
        a[1]= rl_rh_rs[1];
        a[2]= rs;
    } else{
        a[0]= cl_ch_cs[0];
        a[1]= cl_ch_cs[1];
        a[2]= cs;
    }
    return a;
}

int main(){
    //number of elements
    int n;
    cin >> n;

    vector<int> v(n);
    // taking input
    for(int i = 0; i<n; i++){
        cin >> v[i];
    }
    // test print
    for(int i = 0; i<n; i++){
        cout << v[i] << " ";
    }
    // tried to flush output buffer
    cout << endl;
    // this is the function call that does not exit
    std::vector<int> l_h_s = max_subarray(v, 0, n-1);

    cout << l_h_s[2] << "\n";
    return 0;
}

This is the output that I got:

bash-4.3$ ./a.out
5
1
2
-20
3
4
1 2 -20 3 4 
7

Answer 2

You need to use debugger or use some debug statements in your code to know where your program got struck. I didn't quite understand the intention of cross_max_subarray function. But inside the function, you are modifying 'i' value in for loops. This is creating problem in the second for loop. i = rt_index; When rt_index is 0, this loop is becoming infinite.