贪心算法节省时间c++代码

贪心算法是一种常用的优化策略，它在每一步选择中都采取在当前状态下最好或最优的选择，希望这样的局部最优解最终能导致全局最优解。然而，并非所有问题都能通过贪心算法得到全局最优解，但它确实可以解决一些特定问题，如最短路径、最小生成树等。

在C++中编写贪心算法，通常需要以下几个步骤：

1. 确定贪心选择策略：首先明确每个决策应如何依据现有信息做出"最佳"选择。

2. 编写函数：为每次贪心选择实现一个函数，处理当前状态并更新结果。

3. 主循环：按照贪心策略依次执行这些函数，记录中间结果。

4. 检查算法是否结束：有些贪心算法会在满足某个终止条件时停止。

下面是一个简单的例子，展示如何使用贪心算法找到数组中的最大连续子数组和，也称为Kadane's Algorithm:

#include <vector>
#include <climits>

int maxSubarraySum(std::vector<int>& nums) {
    int curr_max = nums[0];
    int global_max = nums[0];

    for (size_t i = 1; i < nums.size(); ++i) {
        curr_max = std::max(nums[i], curr_max + nums[i]);
        global_max = std::max(global_max, curr_max);
    }
    
    return global_max;
}

// 示例
int main() {
    std::vector<int> nums{-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int result = maxSubarraySum(nums);
    std::cout << "Max subarray sum is: " << result << std::endl;
    return 0;
}