分治法求最大子段和c++

分治法求解最大子段和通常涉及到Kadane's Algorithm（卡特兰算法），这是一种用于解决动态规划问题的经典策略，常用于处理数组中的连续子数组之和。在C++中，它的核心思想是将问题分解成更小的子问题，然后合并子问题的结果。

以下是一个简单的C++实现：

#include <vector>
int maxSubArraySum(std::vector<int>& nums) {
    int max_current = nums[0]; // 当前最大子数组和
    int max_global = nums[0]; // 最大全局子数组和

    for (int i = 1; i < nums.size(); ++i) {
        max_current = std::max(nums[i], max_current + nums[i]); // 更新当前最大子数组和
        if (max_current > max_global)
            max_global = max_current; // 如果当前更大，更新全局最大值
    }
    return max_global;
}

在这个函数中，`nums`是一个整数向量，`max_current`记录了从当前位置开始到当前位置的最大子数组和，而`max_global`则保持整个过程中最大的子数组和。遍历数组时，每次迭代都检查是否应该从当前位置开始一个新的子数组，或是继续添加元素到当前的最大子数组。

相关问题

分治法实现最大子段和 C++

以下是使用分治法实现最大子段和的C++代码：

#include <iostream>
#include <algorithm>
using namespace std;

int maxCrossingSum(int arr[], int l, int m, int h)
{
    int sum = 0;
    int left_sum = INT_MIN;
    for (int i = m; i >= l; i--)
    {
        sum = sum + arr[i];
        if (sum > left_sum)
            left_sum = sum;
    }
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = m + 1; i <= h; i++)
    {
        sum = sum + arr[i];
        if (sum > right_sum)
            right_sum = sum;
    }
    return left_sum + right_sum;
}

int maxSubArraySum(int arr[], int l, int h)
{
    if (l == h)
        return arr[l];
    int m = (l + h) / 2;
    return max(max(maxSubArraySum(arr, l, m),
                   maxSubArraySum(arr, m + 1, h)),
               maxCrossingSum(arr, l, m, h));
}

int main()
{
    int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n - 1);
    cout << "Maximum contiguous sum is " << max_sum << endl;
    return 0;
}

用分治法解决最大子段和问题并求出最大子段和及下标范围C++

分治法通常用于复杂问题的递归分解，对于最大子段和问题（也称为Kadane's algorithm），它通过将序列分割成两个部分来查找每个部分的最大子段和，然后合并这两个结果来找到整个数组的最大子段和。以下是使用C++实现的基本思路：

#include <vector>
#include <climits>

// 辅助函数，返回给定区间内的最大子段和
int maxCrossingSum(const std::vector<int>& nums, int low, int mid, int high) {
    int leftMax = INT_MIN;
    int sum = 0;
    for (int i = mid; i >= low; --i) {
        sum += nums[i];
        if (sum > leftMax)
            leftMax = sum;
    }
    
    int rightMax = INT_MIN;
    sum = 0;
    for (int i = mid + 1; i <= high; ++i) {
        sum += nums[i];
        if (sum > rightMax)
            rightMax = sum;
    }

    return leftMax + rightMax;
}

// 主函数，计算整个数组的最大子段和
std::pair<int, std::pair<int, int>> kadanesAlgorithm(const std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0)
        return {0, {0, 0}};

    int maxSoFar = nums[0], currentMax = nums[0];

    int start = 0, end = 0;
    for (int i = 1; i < n; ++i) {
        // 如果当前元素加上前缀和大于当前最大值，更新最大值和起始位置
        if (nums[i] + currentMax > maxSoFar) {
            maxSoFar = nums[i] + currentMax;
            start = i - currentMax;
            end = i;
        }
        
        // 如果当前元素本身大于最大子段和，更新最大子段和
        if (nums[i] > currentMax) {
            currentMax = nums[i];
            start = i;
            end = i;
        }
    }

    return {maxSoFar, {start, end}};
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    auto result = kadanesAlgorithm(nums);
    std::cout << "最大子段和: " << result.first << "\n";
    std::cout << "子段下标范围: [" << result.second.first << ", " << result.second.second << "]" << std::endl;

    return 0;
}

在这个程序中，`kadanesAlgorithm`函数是核心，它首先检查整个数组是否为空，然后遍历数组，维护两个变量`maxSoFar`和`currentMax`分别记录到目前为止的最大子段和以及从当前位置开始的最大子段和。`start`和`end`变量用来保存最大子段和的起始和结束索引。