最大子段和3 c++代码

### 最大子段和问题的C++实现 最大子段和问题是算法领域中的经典问题，其目标是从一个整数数组中找到连续子数组的最大和。以下是几种常见的算法实现方式，包括蛮力法、分治法和动态规划法。 #### 蛮力法 蛮力法通过三重循环枚举所有可能的子段，并计算它们的和以找到最大值。这种方法的时间复杂度为 \(O(n^3)\)，但可以通过优化降低到 \(O(n^2)\) [^1]。以下是一个优化后的 C++ 实现代码： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, max_sum = INT32_MIN; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) { int sum = 0; for (int j = i; j < n; ++j) { sum += a[j]; if (sum > max_sum) max_sum = sum; } } cout << max_sum << endl; return 0; } ``` #### 分治法 分治法将数组分为左右两部分，递归地求解左右两部分的最大子段和，并计算跨越中间点的最大子段和。最终结果为这三者中的最大值。分治法的时间复杂度为 \(O(n \log n)\) [^2]。以下是一个 C++ 实现代码： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int find_max_crossing_subarray(const vector<int>& a, int left, int mid, int right) { int left_sum = INT32_MIN, sum = 0; for (int i = mid; i >= left; --i) { sum += a[i]; if (sum > left_sum) left_sum = sum; } int right_sum = INT32_MIN, sum2 = 0; for (int i = mid + 1; i <= right; ++i) { sum2 += a[i]; if (sum2 > right_sum) right_sum = sum2; } return left_sum + right_sum; } int divide_and_conquer(const vector<int>& a, int left, int right) { if (left == right) return a[left]; int mid = (left + right) / 2; int left_max = divide_and_conquer(a, left, mid); int right_max = divide_and_conquer(a, mid + 1, right); int cross_max = find_max_crossing_subarray(a, left, mid, right); return max({left_max, right_max, cross_max}); } int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; cout << divide_and_conquer(a, 0, n - 1) << endl; return 0; } ``` #### 动态规划法 动态规划是解决最大子段和问题的最优方法之一，其核心思想是利用递推公式 \(C[i] = \max(C[i-1] + a[i], a[i])\) 来计算以每个位置结尾的最大子段和。最终答案为所有 \(C[i]\) 中的最大值。动态规划的时间复杂度为 \(O(n)\) [^3]。以下是一个 C++ 实现代码： ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, max_sum = INT32_MIN, current_sum = 0; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) { current_sum = max(a[i], current_sum + a[i]); max_sum = max(max_sum, current_sum); } cout << max_sum << endl; return 0; } ``` ### 总结 上述三种方法分别对应了不同时间复杂度的解决方案。蛮力法适合理解问题的本质，但效率低下；分治法提供了较好的平衡；动态规划则是最优解法。