求解最大子数组问题

最大子数组：数组A的和最大的非空连续子数组。

最大子数组.png

考虑使用分治策略来求解。因此要将子数组划分为两个规模尽量相等的子数组，也就是找到数组A（假设从low->high）的中间位置mid，然后再求解A[low..mid]和A[mid+1..high]。

A[low..high]的任何连续子数组A必然是以下三种情况之一：

status.png

我们可以递归的求解位于A[low..mid]和A[mid+1,high]的最大子数组，因为这两个子问题依然是最大子数组问题，知识规模更小。剩下的我们就是寻找跨越中点的最大子数组，然后在这三种情况里选择和最大的。

寻找跨越中点的最大子数组代码：

typedef std::tuple<int, int, int> RetType;
RetType findMaxCrossingSubArray(std::vector<int>& vec, int low, int mid, int high) {
    int left_sum = INT_MIN;
    int left_mark = 0;
    int sum = 0;
    for (int i = mid; i >= low; --i) {
        sum += vec[i];
        if (sum > left_sum) {
            left_sum = sum;
            left_mark = i;
        }
    }
    int right_sum = INT_MIN;
    int right_mark = 0;
    sum = 0;
    for (int j = mid+1; j <= high; ++j) {
        sum += vec[j];
        if (sum > right_sum) {
            right_sum = sum;
            right_mark = j;
        }
    }
    return std::make_tuple(left_mark, right_mark, left_sum+right_sum);
}

left-sum是记录左边最大子数组的和的，left-mark记录最大子数组的下标。最后返回一个包含最大子数组的和、最大子数组的左下标和右下标的元组。

剩下就是递归求解那两个子问题，并和跨越中点的最大子数组对比，返回一个最大子数组。

RetType findMaxSubArray(std::vector<int>& vec, int low, int high) {
    if (low == high)
        return std::make_tuple(low, high,vec[low]);
    else {
        int mid = (low+high) / 2;
        int left_low, left_high, left_sum;
        std::tie(left_low, left_high, left_sum) = findMaxSubArray(vec, low, mid);
        int right_low, right_high, right_sum;
        std::tie(right_low, right_high, right_sum) = findMaxSubArray(vec, mid+1, high);
        int cross_low, cross_high, cross_sum;
        std::tie(cross_low, cross_high, cross_sum) = findMaxCrossingSubArray(vec, low, mid, high);
        if (left_sum >= right_sum && left_sum >= cross_sum)
            return std::make_tuple(left_low, left_high, left_sum);
        else if (right_sum >= left_sum && right_sum >= cross_sum)
            return std::make_tuple(right_low, right_high, right_sum);
        else
            return std::make_tuple(cross_low, cross_high, cross_sum);
    }
}

下面给出完整代码：

#include <climits>
#include <cstdio>
#include <tuple>
#include <vector>

class Solution {
public:
    typedef std::tuple<int, int, int> RetType;
    RetType findMaxCrossingSubArray(std::vector<int>& vec, int low, int mid, int high) {
        int left_sum = INT_MIN;
        int left_mark = 0;
        int sum = 0;
        for (int i = mid; i >= low; --i) {
            sum += vec[i];
            if (sum > left_sum) {
                left_sum = sum;
                left_mark = i;
            }
        }
        int right_sum = INT_MIN;
        int right_mark = 0;
        sum = 0;
        for (int j = mid+1; j <= high; ++j) {
            sum += vec[j];
            if (sum > right_sum) {
                right_sum = sum;
                right_mark = j;
            }
        }
        return std::make_tuple(left_mark, right_mark, left_sum+right_sum);
    }

    RetType findMaxSubArray(std::vector<int>& vec, int low, int high) {
        if (low == high)
            return std::make_tuple(low, high,vec[low]);
        else {
            int mid = (low+high) / 2;
            int left_low, left_high, left_sum;
            std::tie(left_low, left_high, left_sum) = findMaxSubArray(vec, low, mid);
            int right_low, right_high, right_sum;
            std::tie(right_low, right_high, right_sum) = findMaxSubArray(vec, mid+1, high);
            int cross_low, cross_high, cross_sum;
            std::tie(cross_low, cross_high, cross_sum) = findMaxCrossingSubArray(vec, low, mid, high);
            if (left_sum >= right_sum && left_sum >= cross_sum)
                return std::make_tuple(left_low, left_high, left_sum);
            else if (right_sum >= left_sum && right_sum >= cross_sum)
                return std::make_tuple(right_low, right_high, right_sum);
            else
                return std::make_tuple(cross_low, cross_high, cross_sum);
        }
    }
};

int main() {
    std::vector<int> vec = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
    int low, high, sum;
    Solution solution;
    std::tie(low, high, sum) = solution.findMaxSubArray(vec, 0, vec.size()-1);
    printf("%d, %d, %d", low, high, sum);
    return 0;
}
// 输出
7 10 43

部分执行过程如下：

partprocess.png