对任意动态生成的n个整数(可含负数)，求最大子段及其和。(其详细的解法参见教材！) 具体要求： 1.采用至少三种方法进行求解： (1)蛮力方法(枚举方法)； (2)分治策略； (3)动态规划方法。 2.对算法和数据进行类的封装，编写好构造函数和析构函数： 3.对任意给定的n个整数，要求对以上的三种算法，都能够输出最大子段及其和。注：教材中，对于分治策略及动态规划方法，并没有给出最大子段，只是给出了最大

子段和。因此，本题中要求输出最大子段及其和。

以下是对应的代码实现：

1. 蛮力方法

#include <iostream>
#include <vector>

using namespace std;

class MaxSubarray {
public:
    MaxSubarray(vector<int>& nums) : nums(nums) {}

    void brute_force() {
        int len = nums.size();
        int max_sum = INT_MIN;
        int start = -1, end = -1;

        for (int i = 0; i < len; i++) {
            int sum = 0;
            for (int j = i; j < len; j++) {
                sum += nums[j];
                if (sum > max_sum) {
                    max_sum = sum;
                    start = i;
                    end = j;
                }
            }
        }

        cout << "Brute Force: " << max_sum << endl;
        cout << "Max Subarray: ";
        for (int i = start; i <= end; i++) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }

private:
    vector<int> nums;
};

int main() {
    vector<int> nums = {1, -2, 3, 10, -4, 7, 2, -5};
    MaxSubarray ms(nums);

    ms.brute_force();

    return 0;
}

2. 分治策略

#include <iostream>
#include <vector>

using namespace std;

class MaxSubarray {
public:
    MaxSubarray(vector<int>& nums) : nums(nums) {}

    void divide_and_conquer() {
        int len = nums.size();
        int max_sum = INT_MIN;
        int start = -1, end = -1;

        divide_and_conquer_helper(0, len - 1, max_sum, start, end);

        cout << "Divide and Conquer: " << max_sum << endl;
        cout << "Max Subarray: ";
        for (int i = start; i <= end; i++) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }

private:
    vector<int> nums;

    void divide_and_conquer_helper(int left, int right, int& max_sum, int& start, int& end) {
        if (left == right) {
            max_sum = nums[left];
            start = left;
            end = right;
            return;
        }

        int mid = left + (right - left) / 2;
        int left_max_sum = INT_MIN, left_start, left_end;
        int right_max_sum = INT_MIN, right_start, right_end;
        int cross_max_sum = INT_MIN, cross_start, cross_end;

        divide_and_conquer_helper(left, mid, left_max_sum, left_start, left_end);
        divide_and_conquer_helper(mid + 1, right, right_max_sum, right_start, right_end);

        int sum = 0;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > cross_max_sum) {
                cross_max_sum = sum;
                cross_start = i;
            }
        }

        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            if (sum > cross_max_sum) {
                cross_max_sum = sum;
                cross_end = i;
            }
        }

        max_sum = max(left_max_sum, right_max_sum);
        max_sum = max(max_sum, cross_max_sum);

        if (max_sum == left_max_sum) {
            start = left_start;
            end = left_end;
        } else if (max_sum == right_max_sum) {
            start = right_start;
            end = right_end;
        } else {
            start = cross_start;
            end = cross_end;
        }
    }
};

int main() {
    vector<int> nums = {1, -2, 3, 10, -4, 7, 2, -5};
    MaxSubarray ms(nums);

    ms.divide_and_conquer();

    return 0;
}

3. 动态规划方法

#include <iostream>
#include <vector>

using namespace std;

class MaxSubarray {
public:
    MaxSubarray(vector<int>& nums) : nums(nums) {}

    void dynamic_programming() {
        int len = nums.size();
        int max_sum = INT_MIN;
        int start = -1, end = -1;

        vector<int> dp(len);
        dp[0] = nums[0];

        for (int i = 1; i < len; i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            if (dp[i] > max_sum) {
                max_sum = dp[i];
                end = i;
            }
        }

        // find the start index
        for (int i = end; i >= 0; i--) {
            if (max_sum == dp[i]) {
                start = i;
                break;
            }
        }

        cout << "Dynamic Programming: " << max_sum << endl;
        cout << "Max Subarray: ";
        for (int i = start; i <= end; i++) {
            cout << nums[i] << " ";
        }
        cout << endl;
    }

private:
    vector<int> nums;
};

int main() {
    vector<int> nums = {1, -2, 3, 10, -4, 7, 2, -5};
    MaxSubarray ms(nums);

    ms.dynamic_programming();

    return 0;
}