最大子段和c++

### 最大子段和算法的 C++ 实现 最大子段和问题是经典的动态规划问题之一，其目标是从给定的一维数组中找到连续子数组的最大和。以下是几种常见的 C++ 实现方式。 #### 方法一：基于动态规划的经典实现 此方法通过维护一个 `dp` 数组来存储当前最优解的状态转移方程为 \( dp[i] = \max(dp[i-1] + arr[i], arr[i]) \)[^1]。最终结果可以通过遍历整个 `dp` 数组得到最大值。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; void MaximumSum(vector<int> V) { int size = V.size(); int DP[size + 1]; // 初始化 DP 数组 for (int i = 0; i <= size; ++i) DP[i] = 0; // 动态规划计算过程 for (int i = 1; i <= size; ++i) { DP[i] = max(DP[i - 1] + V[i - 1], V[i - 1]); } // 输出中间状态（可选） cout << "不同长度下的最大子段和分别为：" << endl; for (int i = 0; i <= size; ++i) cout << DP[i] << " "; cout << endl; // 找到全局最大值 int answer = 0; for (int i = 0; i <= size; ++i) { if (DP[i] > answer) answer = DP[i]; } cout << "最大子段和为: " << answer << endl; } int main() { vector<int> V; int n, temp; cin >> n; for (int i = 0; i < n; ++i) { cin >> temp; V.push_back(temp); } MaximumSum(V); return 0; } ``` --- #### 方法二：空间复杂度优化版本 为了减少额外的空间开销，可以仅使用两个变量代替完整的 `dp` 数组。这种方法的核心思想是实时更新当前的最大子段和以及整体的最大值[^2]。 ```cpp #include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long n, maxx = LLONG_MIN, a, s = 0; cin >> n; for(int i = 1; i <= n; ++i){ cin >> a; if(s > 0){ s += a; } else{ s = a; } maxx = max(maxx, s); } cout << maxx; return 0; } ``` --- #### 方法三：带有起始与结束索引的实现 除了返回最大子段和外，还可以进一步扩展功能以获取对应的起始和终止位置[^3]。 ```cpp #include <iostream> #include <vector> using namespace std; struct Result { int sum; int startIndex; int endIndex; }; Result maxSubArray(const vector<int>& nums) { int currentMax = 0; int globalMax = INT_MIN; int start = 0, end = 0, s = 0; for (size_t i = 0; i < nums.size(); ++i) { if (currentMax >= 0) { currentMax += nums[i]; } else { currentMax = nums[i]; s = i; } if (globalMax < currentMax) { globalMax = currentMax; start = s; end = i; } } return {globalMax, start, end}; } int main() { vector<int> nums; int num; cout << "输入数据:"; while (cin >> num && cin.peek() != '\n') { nums.push_back(num); } auto result = maxSubArray(nums); cout << "最大子段和:" << result.sum << "\n"; cout << "起始位置:" << result.startIndex + 1 << "\n"; cout << "终止位置:" << result.endIndex + 1 << "\n"; return 0; } ``` --- #### 方法四：完整版带打印路径的结果 如果不仅需要知道最大子段和，还需要输出具体的子数组，则可以在动态规划过程中记录路径信息并回溯获得具体区间[^4]。 ```cpp #include <iostream> using namespace std; const int MAXN = 1e5 + 7; long long a[MAXN]; pair<long long, pair<int, int>> maxFind(int n) { long long b = 0, sum = LLONG_MIN; int bestStart = 0, bestEnd = 0, currentStart = 0; for (int j = 0; j < n; ++j) { if (b > 0) { b += a[j]; } else { b = a[j]; currentStart = j; } if (b > sum) { sum = b; bestStart = currentStart; bestEnd = j; } } cout << "最大子段为: "; for (int k = bestStart; k <= bestEnd; ++k) { cout << a[k] << ' '; } cout << endl; return {sum, {bestStart, bestEnd}}; } int main() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; pair<long long, pair<int, int>> res = maxFind(n); cout << "最大子段和为: " << res.first << endl; return 0; } ``` ---