给定n 个整数(可以为负数)的序列<a1, a2, … , an>,求: image.png 【输入形式】输入整数个数n,整数序列 【输出形式】最大字段和及相应子序列 【样例输入】 6 -2 11 -4 13 -5 -2 【样例输出】 20 11 -4 13 编写c++代码
时间: 2024-03-06 22:46:50 浏览: 50
以下是使用动态规划求解最大字段和的 C++ 代码:
```
#include <iostream>
#include <vector>
using namespace std;
// 动态规划求解最大字段和
int max_subarray_sum(const vector<int>& nums, vector<int>& subarray) {
int n = nums.size();
vector<int> dp(n); // dp[i] 表示以 nums[i] 结尾的最大字段和
dp[0] = nums[0];
int max_sum = dp[0];
int start = 0, end = 0; // 最大字段和对应的子序列下标范围
for (int i = 1; i < n; i++) {
if (dp[i - 1] > 0) {
dp[i] = dp[i - 1] + nums[i];
} else {
dp[i] = nums[i];
start = i;
}
if (dp[i] > max_sum) {
max_sum = dp[i];
end = i;
}
}
subarray.clear();
for (int i = start; i <= end; i++) {
subarray.push_back(nums[i]);
}
return max_sum;
}
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
vector<int> subarray;
int max_sum = max_subarray_sum(nums, subarray);
cout << max_sum << " ";
for (int i = 0; i < subarray.size(); i++) {
cout << subarray[i] << " ";
}
return 0;
}
```
输入样例:
```
6
-2 11 -4 13 -5 -2
```
输出样例:
```
20 11 -4 13
```