c++中如何实现动态规划求最大子数组和_c++动态规划最大子数组和实现-C++-PHP中文网

c++中如何实现动态规划求最大子数组和_c++动态规划最大子数组和实现

冰火之心

发布： 2025-09-30 18:32:02

原创

422人浏览过

最大子数组和可通过动态规划求解，定义currentSum为以当前元素结尾的最大和，maxSum记录全局最大值；状态转移方程为currentSum = max(nums[i], currentSum + nums[i])，每步更新maxSum；实现时仅需两个变量，时间复杂度O(n)，空间复杂度O(1)；初始化从nums[0]开始，遍历过程中持续更新currentSum与maxSum，最终返回maxSum；适用于包含负数的数组，能正确处理边界情况如空数组或单元素数组。

c++中如何实现动态规划求最大子数组和_c++动态规划最大子数组和实现

在C++中，使用动态规划求解最大子数组和是一个经典问题，通常称为“最大连续子数组和”或“Kadane算法”。核心思想是：每一步决策都保留以当前位置结尾的最大子数组和，从而逐步推导出全局最大值。

动态规划思路解析

定义状态：dp[i] 表示以第 i 个元素结尾的最大子数组和。由于只需要前一个状态，可以优化空间，只用一个变量记录当前最大和。

状态转移方程为：

dp[i] = max(nums[i], dp[i-1] + nums[i])

立即学习“C++免费学习笔记（深入）”；

即：要么从当前元素重新开始，要么将当前元素加入前面的子数组。

Robovision AI

一个强大的视觉AI管理平台

查看详情

C++实现代码

以下是基于动态规划的简洁实现，时间复杂度 O(n)，空间复杂度 O(1)：

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int maxSubArray(vector<int>& nums) {
    if (nums.empty()) return 0;

    int maxSum = nums[0];        // 全局最大和
    int currentSum = nums[0];    // 当前子数组和

    for (int i = 1; i < nums.size(); ++i) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }

    return maxSum;
}

// 测试示例
int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << "最大子数组和为：" << maxSubArray(arr) << endl;
    return 0;
}

登录后复制