C++函数如何返回三个元素？——《算法导论》最大子数组问题伪代码转化咨询

Hey there! Let's figure out how to return three values (low, high, sum) from a C++ function for the maximum subarray problem, just like the pseudocode from Introduction to Algorithms specifies. There are a few straightforward, idiomatic ways to do this in C++—let's break them down one by one.

1. Use a Custom Struct (Most Readable) #

This is my go-to approach because it makes your code super clear. You can define a struct that exactly matches the three values you need to return, which mirrors the pseudocode's return structure perfectly.

Here's how it would look:

#include <iostream>
#include <climits> // For INT_MIN

// Define a struct to hold the maximum subarray result
struct MaxSubarrayResult {
    int low;    // Starting index of the maximum subarray
    int high;   // Ending index of the maximum subarray
    long long sum; // Sum of the maximum subarray (use long long to avoid overflow)
};

// Example implementation of the divide-and-conquer maximum subarray function
MaxSubarrayResult find_max_crossing_subarray(int arr[], int low, int mid, int high) {
    MaxSubarrayResult result;
    long long left_sum = LLONG_MIN;
    long long sum = 0;
    int max_left = mid;

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

    long long right_sum = LLONG_MIN;
    sum = 0;
    int max_right = mid + 1;

    for (int j = mid + 1; j <= high; ++j) {
        sum += arr[j];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = j;
        }
    }

    result.low = max_left;
    result.high = max_right;
    result.sum = left_sum + right_sum;
    return result;
}

MaxSubarrayResult find_max_subarray(int arr[], int low, int high) {
    if (high == low) {
        return {low, high, arr[low]};
    } else {
        int mid = (low + high) / 2;
        MaxSubarrayResult left = find_max_subarray(arr, low, mid);
        MaxSubarrayResult right = find_max_subarray(arr, mid + 1, high);
        MaxSubarrayResult cross = find_max_crossing_subarray(arr, low, mid, high);

        if (left.sum >= right.sum && left.sum >= cross.sum) {
            return left;
        } else if (right.sum >= left.sum && right.sum >= cross.sum) {
            return right;
        } else {
            return cross;
        }
    }
}

int main() {
    int arr[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    MaxSubarrayResult result = find_max_subarray(arr, 0, n - 1);

    std::cout << "Maximum subarray starts at index " << result.low 
              << ", ends at index " << result.high 
              << ", with sum: " << result.sum << std::endl;
    return 0;
}

The best part here is that anyone reading your code immediately understands what MaxSubarrayResult represents—no guessing required.

2. Use std::tuple (Lightweight, No Custom Type) #

If you don't want to define a separate struct, you can use std::tuple from the C++ standard library. It lets you package multiple values of different types into a single return value.

Here's how to adapt the function:

#include <iostream>
#include <climits>
#include <tuple> // For std::tuple

using namespace std;

tuple<int, int, long long> find_max_crossing_subarray(int arr[], int low, int mid, int high) {
    long long left_sum = LLONG_MIN;
    long long sum = 0;
    int max_left = mid;

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

    long long right_sum = LLONG_MIN;
    sum = 0;
    int max_right = mid + 1;

    for (int j = mid + 1; j <= high; ++j) {
        sum += arr[j];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = j;
        }
    }

    return make_tuple(max_left, max_right, left_sum + right_sum);
}

tuple<int, int, long long> find_max_subarray(int arr[], int low, int high) {
    if (high == low) {
        return make_tuple(low, high, (long long)arr[low]);
    } else {
        int mid = (low + high) / 2;
        auto left = find_max_subarray(arr, low, mid);
        auto right = find_max_subarray(arr, mid + 1, high);
        auto cross = find_max_crossing_subarray(arr, low, mid, high);

        long long left_sum = get<2>(left);
        long long right_sum = get<2>(right);
        long long cross_sum = get<2>(cross);

        if (left_sum >= right_sum && left_sum >= cross_sum) {
            return left;
        } else if (right_sum >= left_sum && right_sum >= cross_sum) {
            return right;
        } else {
            return cross;
        }
    }
}

int main() {
    int arr[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    auto [low, high, sum] = find_max_subarray(arr, 0, n - 1); // C++17 structured binding

    cout << "Maximum subarray starts at index " << low 
         << ", ends at index " << high 
         << ", with sum: " << sum << endl;
    return 0;
}

Note that with C17 and later, you can use structured bindings (auto [low, high, sum]) to unpack the tuple cleanly. Before C17, you'd have to use std::get<0>(result), std::get<1>(result), etc., which is a bit less readable.

3. Pass Values by Reference (Avoid Returning a Complex Type) #

Another option is to pass low, high, and sum as reference parameters to your function. The function will modify these variables directly instead of returning a value.

Here's an example:

#include <iostream>
#include <climits>

void find_max_crossing_subarray(int arr[], int low, int mid, int high, 
                                int& out_low, int& out_high, long long& out_sum) {
    long long left_sum = LLONG_MIN;
    long long sum = 0;
    int max_left = mid;

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

    long long right_sum = LLONG_MIN;
    sum = 0;
    int max_right = mid + 1;

    for (int j = mid + 1; j <= high; ++j) {
        sum += arr[j];
        if (sum > right_sum) {
            right_sum = sum;
            max_right = j;
        }
    }

    out_low = max_left;
    out_high = max_right;
    out_sum = left_sum + right_sum;
}

void find_max_subarray(int arr[], int low, int high, 
                       int& out_low, int& out_high, long long& out_sum) {
    if (high == low) {
        out_low = low;
        out_high = high;
        out_sum = arr[low];
        return;
    } else {
        int mid = (low + high) / 2;
        int left_low, left_high;
        long long left_sum;
        find_max_subarray(arr, low, mid, left_low, left_high, left_sum);

        int right_low, right_high;
        long long right_sum;
        find_max_subarray(arr, mid + 1, high, right_low, right_high, right_sum);

        int cross_low, cross_high;
        long long cross_sum;
        find_max_crossing_subarray(arr, low, mid, high, cross_low, cross_high, cross_sum);

        if (left_sum >= right_sum && left_sum >= cross_sum) {
            out_low = left_low;
            out_high = left_high;
            out_sum = left_sum;
        } else if (right_sum >= left_sum && right_sum >= cross_sum) {
            out_low = right_low;
            out_high = right_high;
            out_sum = right_sum;
        } else {
            out_low = cross_low;
            out_high = cross_high;
            out_sum = cross_sum;
        }
    }
}

int main() {
    int arr[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int low, high;
    long long sum;

    find_max_subarray(arr, 0, n - 1, low, high, sum);

    std::cout << "Maximum subarray starts at index " << low 
              << ", ends at index " << high 
              << ", with sum: " << sum << std::endl;
    return 0;
}

This approach works well if you prefer not to deal with return types of custom structures or tuples, but it can make the function signature a bit cluttered.

Which Should You Choose? #

• Struct: Go for this if readability is your top priority—this is the most self-documenting option.
• Tuple: Use this when you want a quick, standard-library solution without defining a new type (great for small, one-off cases).
• Reference Parameters: This is useful if you need to avoid copying large objects (though in this case, the overhead is negligible) or if you're working with older C++ standards that don't support structured bindings.

内容的提问来源于stack exchange，提问作者Dani Suba