Returning a tuple from a function in C

Question

I need some hint for implementing this algorithm in C. This is a maximum subarray problem. I have made the polynomial time program and also linear time program. I am new to C so I don't know how to return multiple values from a function as this algorithm requires it. For example this line in the algorithm (left-low,left-high,left-sum)=FIND-MAXIMUM-SUBARRAY(A,low,mid) where FIND-MAX-SUBARRAY(A,low,mid) is a recursive function call.

This is the algorithm from coremen:

Below I have set the global variables cross-low,cross-high,cross-sum . How can I do the same for left-low,left-high,left-sum and right-low,right-high,right-sum?

#include "max_subarray_common.h"
#define SENTINAL -3000

int left_low,left_high,left_sum;
int right_low,right_high,right_sum;
int cross_low,cross_high,cross_sum;


void max_crossing_subarray(int low,int mid,int high)
{
    int left_sum=SENTINAL;
    int sum=0;
    int max_left=low,max_right=high;
    for(int i=mid;i>=low;i--)
    {
        sum=sum+change[i];
        if(sum>left_sum)
        {
            left_sum=sum;
            max_left=i;
        }
    }
    int right_sum=0;
    sum=0;
    for(int j=mid+1;j<=high;j++)
    {
        sum=sum+change[j];
        if(sum>right_sum)
        {
            right_sum=sum;
            max_right=j;
        }
    }
    cross_low=max_left;
    cross_high=max_right;
    cross_sum=left_sum+right_sum;
}

This is my header file:

#ifndef max_subarray_h
#define max_subarray_h

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

extern int price[];
extern int n;
extern int change[];
extern int from;
extern int to;
extern int max;


void init_change();
void max_subarray_poly();
void max_subarray_crossing();
void max_subarray_rec();
void max_crossing_subarray();

#endif

change[] is the array for which the subarray is to be found. Also my output should look like this:

from=8
to=11
maximum profit=43

Answer 1

You can achieve the objective by defining a structure using the keyword 'struct' that will hold the three variables you intend to return. To do this, add structure definition at the Header section of your c program.

typedef struct left {  
  int left_low;  
  int left_high;
  int left_sum;
}LEFT;

Define a variable of type LEFT in your main (or where you want to use it) Note. Return type of your FIND-MAXIMUM-SUBARRAY will be LEFT. You also need to pass your variable 'stleft' to your FIND-MAXIMUM-SUBARRAY function.

LEFT stleft;

Allocate memory to stleft

stleft = malloc(sizeof(LEFT));

Assign values to be returned , to your variable "stleft"

stleft.left_low = max_left;
stleft.left_high = max_left;
stleft.left_sum = left_sum + right_sum;

Return your variable

return stleft;

Accessing left_low in stleft

int newvar1;
newvar1 = stleft.left_low;

For more help lookup C structures

Answer 2

The function computes 3 different indicators for the set of arguments, there are multiple ways to return multiple results:

• add extra arguments, one for each result, as pointers to int or whatever type is more appropriate. Store the results indirectly into the variables whose addresses have been passed by the caller before returning a completion code.

• add an extra argument to the function, pointer to a structure with one member per result, and populate this structure before return a success code to the caller.

• return such a structure by value. This approach is less idiomatic in C because it was not part of the original pre-Ansi C specification. This was a long time ago, more than 30 years, but it is still frowned upon by many programmers. Another downside of this approach is that you cannot return a failure indication easily. As can be seen from the OP's own usage of this solution, it can lead to very ineffective coding practices.

• allocate a structure for the results and return the pointer to the caller. You may indicate failure by returning NULL, but it is less informative than an error code. The life cycle of this structure is error prone: this pointer may get lost if the return value is not stored, care must be taken to free it at the appropriate time.

Returning such results via global variables is definitely not a good solution, for reasons explained in the other answers. The second option above is the one I would recommend.