最大子序列和问题c++

最大子序列和问题（Maximum Subarray Problem），也称为 Kadane's Algorithm，在C++中是一个经典的问题，通常用于寻找一个数组中连续元素的最大和。该算法的核心思想是从左到右遍历数组，维护两个变量：当前子序列和（current sum），以及全局最大子序列和（global max sum）。对于每个元素，有两种选择：要么将其加入当前子序列，要么从零开始创建一个新的子序列。

以下是C++实现这个算法的一个简单版本：

#include <climits>
int maxSubArraySum(int arr[], int size) {
    int current_sum = arr[0]; // 初始化当前子序列和为第一个元素
    int global_max_sum = arr[0]; // 初始化全局最大子序列和

    for (int i = 1; i < size; ++i) {
        current_sum = std::max(arr[i], current_sum + arr[i]); // 如果加上当前值更大，就合并；否则从零开始
        global_max_sum = std::max(global_max_sum, current_sum); // 更新全局最大子序列和
    }

    return global_max_sum;
}