Finding a maximum sum contiguous sub array

tryingToLearn

I am writing a code to find the maximum sum contiguous sub array in C. The logic seems fine according to me, but still the output is not correct. Please look into the code. The algorithm divides a bigger array into 2 sub-arrays. It then checks for maximum sum sub-array by examining the left array , right array and also the array containing the midpoint (It will check right and left from the midpoint and then return the maximum sum sub-array containing the midpoint).

int* cross_max(int arr[], int low, int mid, int high)
{
    int left_max, left_sum = -2000;
    int sum = 0;
    int i;
    for(i=mid; i>=low;i--)
    {
        sum = sum + arr[i];
        if(sum > left_sum)
        {
            left_sum = sum;
            left_max = i;
        }
    }


    int right_max, right_sum = -2000;

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

    // 0 - sum
    // indices - 1,2

    int temp_arr[3] = {0,0,0};
    temp_arr[0] = left_sum + right_sum;
    temp_arr[1] = left_max;
    temp_arr[2] = right_max;

    int *p = temp_arr;

    printf("\n Maximum sum = %d\n",*p);
    printf("\n low = %d\n",*(p+1));
    printf("\n high = %d\n",*(p+2));    

    return p;

}


int* find_max(int arr[], int low, int high)
{
    int temp_arr[3] = {0,0,0};
    if(low == high)
    {
        temp_arr[0] = arr[low];
        temp_arr[1] = low;
        temp_arr[2] = low;

        int *q = temp_arr;
        return q;
    }

    int mid = (low + high)/2; 

    int* a1 =  find_max(arr,low,mid);
    int* a2 =  find_max(arr,mid+1,high);
    int* a3 =  cross_max(arr,low,mid,high);

    if (*a1 > *a2 && *a1 > *a3)
        return a1;

    else if (*a2 > *a1 && *a2 > *a3)
        return a2;

    else
        return a3;

}


int main()
{
    int arr[8] = {1,1,2,-2,3,3,4,-4};

    int *point = find_max(arr,0,7);

    printf("\n Maximum sum = %d\n",*point);
    printf("\n low = %d\n",*(point+1));
    printf("\n high = %d\n",*(point+2));    
    return 0;
}
Some programmer dude

There are a couple of problems with undefined behavior in your code:

The first is that you pass 9 as high which will be used to index the tenth element of an eight-element array. It will be the tenth because in cross_max you loop while i <= high, so you will index arr[9]. Remember that array indexes are from zero to the size minus one (so you can index from 0 to 7 for your array). The indexes out of bounds will contain undefined (i.e. random) values.

The second problem is that you are returning pointers to a local variable from cross_max. This will lead to undefined behavior when you use that returned pointer. Local variables are only valid inside the scope they were declared, and when the function returns the memory area used by the local variables will be reclaimed and used for the next function.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related

From Dev

Counting all contiguous sub-arrays given sum zero

From Dev

Finding the sum of a nested array

From Dev

Finding maximum alternating sum of digits (python 3)

From Dev

Finding sub-matrix with minimum elementwise sum

From Dev

Finding a sub array in an array in Java

From Dev

Dynamic programming finding maximum value of products and sum for elements in array

From Dev

Finding the longest contiguous subsequence in an array

From Dev

Finding a maximum sum contiguous sub array - another version

From Dev

Finding the contiguous sub array with max sum

From Dev

largest sum contiguous sub array using recursion to directly output result

From Dev

Finding indexes of maximum values of an array

From Dev

Finding the sum of an array in javascript

From Dev

Algorithm splitting array into sub arrays where the maximum sum among all sub arrays is as low as possible

From Dev

Find the beginning and end of largest contiguous sub-sequence sum

From Dev

Split an array into equal contiguous subarrays of equal sum

From Dev

Print SubArray of Maximum Contiguous product in Array

From Dev

Finding a maximum sum contiguous sub array

From Dev

Finding the sum of a nested array

From Dev

Finding Count Sum in Array

From Dev

Finding a sub array in an array in Java

From Dev

Returning wrong maximum sum sub array(kadane's algorithm), but correct maximum sum

From Dev

finding the sum of numbers in an array

From Dev

How to get sub array that has maximum sum of all its items

From Dev

Maximum contiguous sum using Divide and Conquer

From Dev

Maximum sum in a contiguous subarray of a given 2D array

From Dev

Maximum Sub-Set Sum

From Dev

Finding Maximum Value of Array

From Dev

Finding a minimum and maximum value in an array

From Dev

Finding pointer to maximum value of array

Related Related

  1. 1

    Counting all contiguous sub-arrays given sum zero

  2. 2

    Finding the sum of a nested array

  3. 3

    Finding maximum alternating sum of digits (python 3)

  4. 4

    Finding sub-matrix with minimum elementwise sum

  5. 5

    Finding a sub array in an array in Java

  6. 6

    Dynamic programming finding maximum value of products and sum for elements in array

  7. 7

    Finding the longest contiguous subsequence in an array

  8. 8

    Finding a maximum sum contiguous sub array - another version

  9. 9

    Finding the contiguous sub array with max sum

  10. 10

    largest sum contiguous sub array using recursion to directly output result

  11. 11

    Finding indexes of maximum values of an array

  12. 12

    Finding the sum of an array in javascript

  13. 13

    Algorithm splitting array into sub arrays where the maximum sum among all sub arrays is as low as possible

  14. 14

    Find the beginning and end of largest contiguous sub-sequence sum

  15. 15

    Split an array into equal contiguous subarrays of equal sum

  16. 16

    Print SubArray of Maximum Contiguous product in Array

  17. 17

    Finding a maximum sum contiguous sub array

  18. 18

    Finding the sum of a nested array

  19. 19

    Finding Count Sum in Array

  20. 20

    Finding a sub array in an array in Java

  21. 21

    Returning wrong maximum sum sub array(kadane's algorithm), but correct maximum sum

  22. 22

    finding the sum of numbers in an array

  23. 23

    How to get sub array that has maximum sum of all its items

  24. 24

    Maximum contiguous sum using Divide and Conquer

  25. 25

    Maximum sum in a contiguous subarray of a given 2D array

  26. 26

    Maximum Sub-Set Sum

  27. 27

    Finding Maximum Value of Array

  28. 28

    Finding a minimum and maximum value in an array

  29. 29

    Finding pointer to maximum value of array

HotTag

Archive