Segmentation fault on maximum subarray code

Question

I am coding the maximum subarray problem on C and am facing a segFault error. I tested the find_max_crossing_subarray function alone and it worked fine. However, when I added the find_maximum_subarray function, the error occurred. Any idea what is wrong with my code?

Thx

#include <stdio.h>
#include <limits.h>

typedef struct Tuple{
    int max_left;
    int max_right;
    int left_plus_right;
}Tuple;


struct Tuple find_max_crossing_subarray(int A[], int low, int mid, int high){
    int left_sum = INT_MIN;
    int sum = 0;
    int i;  
    int max_left;
    int max_right;

    for (i = mid; i >= low; i--){
        sum += A[i];
        if (sum > left_sum){
            left_sum = sum;
            max_left = i;
        }
    }

    int right_sum = INT_MIN;
    sum = 0;

    for (i = mid + 1; i <= high; i++){
        sum += A[i];
        if (sum > right_sum){
            right_sum = sum;
            max_right = i;
        }
    }

    Tuple r = {max_left, max_right, left_sum+right_sum};

    return r;
}

struct Tuple find_maximum_subarray(int A[], int low, int high){
    int mid;        
    Tuple r;
    int left_sum;
    int right_sum;
    int cross_sum;

    if (low == high){
        r.max_left = low;
        r.max_right = high;
        r.left_plus_right = A[low];
        return r;
    }

    else{
        mid = (low+mid)/2;
        Tuple r_left = find_maximum_subarray(A, low, mid);
        Tuple r_right = find_maximum_subarray(A, mid+1, high);
        Tuple r_cross = find_max_crossing_subarray(A,low, mid, high);

        if (left_sum >= cross_sum && left_sum >= right_sum){
            return r_left;
        }

        else if (right_sum >= cross_sum && right_sum >= left_sum){  
            return r_right;
        }

        else{
            return r_cross;
        }

    }
}


int main(){
    int A[10] = {-1,2,4,5,-6,2,-1,4,-5,-1};
    int low = 0;
    int high = 9;
    struct Tuple avg;
    avg = find_maximum_subarray(A, low, high);
    printf("max_left: %d\n",avg.max_left);
    printf("max_right: %d\n",avg.max_right);
    printf("left_plus_right: %d\n",avg.left_plus_right);
}

EDIT: Output of gdb executable then run

Starting program: path_to_executable/maxSubArray 

Program received signal SIGSEGV, Segmentation fault.
0x0804854d in find_maximum_subarray ()

@MattMcNabb I'll try with gdb (but I'm not familiar with debugging tools) — teaLeef
– teaLeef, Commented Aug 4, 2014 at 22:41
@teaLeef It's worth running it under GDB (maybe recompiling with -ggdb) just to see what line is segfaulting. — Patrick Collins
– Patrick Collins, Commented Aug 4, 2014 at 22:47
Also, you typedef the struct as Tuple and then keep referring to it as struct Tuple -- you should probably pick one or the other to do. — Patrick Collins
– Patrick Collins, Commented Aug 4, 2014 at 22:51
It looks like you're using left_sum, right_sum, and cross_sum uninitialized, unless I'm misunderstanding your code. That wouldn't cause a segfault, though. — Patrick Collins
– Patrick Collins, Commented Aug 4, 2014 at 22:55

Patrick Collins · Accepted Answer · 2014-08-04 23:22:51Z

4

I copied your code and ran it under GDB. You're stuck in an infinite loop here:

mid = (low+mid)/2;
Tuple r_left = find_maximum_subarray(A, low, mid);
Tuple r_right = find_maximum_subarray(A, mid+1, high);

Somehow, low = 3 and high = 1. Then mid = 4/2, and it calls r_right = find_maximum_subarray(A, 1, 3) and goes through it again. The segfault is from a stack overflow error.

The first few layers of the callstack looks like this:

#65496 0x00000000004006aa in find_maximum_subarray (A=0x7fffffffde50, low=1, high=-67111995) at so-help.c:59
#65497 0x0000000000400687 in find_maximum_subarray (A=0x7fffffffde50, low=1, high=0) at so-help.c:58
#65498 0x0000000000400687 in find_maximum_subarray (A=0x7fffffffde50, low=1, high=0) at so-help.c:58
#65499 0x0000000000400687 in find_maximum_subarray (A=0x7fffffffde50, low=1, high=9) at so-help.c:58
#65500 0x00000000004006aa in find_maximum_subarray (A=0x7fffffffde50, low=0, high=9) at so-help.c:59

which points to high being used uninitialized.

The issue is:

mid = (low+mid)/2;

where you presumably meant low+high.

Fixing this lets it run without segfaulting, although you still need to fix left_sum, right_sum and cross_sum -- they're also being used uninitialized, and it's not clear what they should be.

In the future, consider compiling with the options -Wuninitialized or -Wall -- gcc found the error for me when I turned them on.

answered Aug 4, 2014 at 23:22

Patrick Collins

10.7k5 gold badges36 silver badges74 bronze badges

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

1 Comment

Patrick Collins Over a year ago

Compiler warnings, GDB and valgrind are a lifesaver when you're writing C.

Collectives™ on Stack Overflow

Segmentation fault on maximum subarray code

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related