c++中如何实现动态规划最大子序和_c++动态规划最大子序和实现方法-C++-PHP中文网

c++中如何实现动态规划最大子序和_c++动态规划最大子序和实现方法

裘德小鎮的故事

发布： 2025-10-10 08:15:01

原创

421人浏览过

最大子序和问题可通过动态规划高效求解，定义currentSum表示以当前元素结尾的最大和，maxSum记录全局最大值，状态转移方程为currentSum = max(nums[i], currentSum + nums[i])，每步更新maxSum，最终返回maxSum。代码实现中仅用两个变量实现O(1)空间复杂度，时间复杂度O(n)，适用于大规模数据处理，且可推广至最大子矩阵等问题。

c++中如何实现动态规划最大子序和_c++动态规划最大子序和实现方法

在C++中，使用动态规划求解“最大子序和”问题是一种高效且经典的方法。该问题要求在一个整数数组中找出连续子数组，使其元素之和最大。

问题描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。

例如：
输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。

动态规划思路

定义状态 dp[i] 表示以第 i 个元素结尾的最大子数组和。

状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])

含义是：要么从当前元素重新开始，要么将当前元素加到前面的子序列上。

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

Chromox

Chromox是一款领先的AI在线生成平台，专为喜欢AI生成技术的爱好者制作的多种图像、视频生成方式的内容型工具平台。

184

查看详情

由于只需要前一个状态，可以只用一个变量代替整个数组，实现空间优化。

C++ 实现代码

以下是使用动态规划实现的完整 C++ 代码：

#include <iostream>
#include <vector>
#include <algorithm>
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> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << "最大子序和为: " << maxSubArray(nums) << endl;
return 0;
}