算法与数据结构精讲：最大子段和（暴力 / 优化 / 分治）+ 线段树从入门到实战

前言最大子段和是最经典的入门题之一而线段树则是处理区间查询、区间更新的高级数据结构是进阶必备。本文将基于我提供的完整代码分两大部分精讲最大子段和问题暴力 O (n³) → 优化 O (n²) → 分治 O (nlogn)线段树Segment Tree原理 构建 区间和查询 完整代码实现所有代码均可直接复制运行复杂度分析、边界处理、核心思路全部讲透。第一部分最大子段和问题一、问题描述给定一个整数数组可包含负数找到连续子数组使其和最大返回这个最大和。数组{-2, 11, -4, 13, -5, -2} 最大子段11 (-4) 13 20 输出20二、解法 1暴力枚举O (n³)思路枚举所有起点 i、终点 j再循环累加 i~j 的和记录最大值。// 暴力破解 O(n³) int MaxSum1(const int* ar, int n) { assert(ar ! nullptr); if (n 1) return 0; int sum 0; int start -1; int end -1; // 枚举起点 i for (int i 0; i n; i) { // 枚举终点 j for (int j i; j n; j) { int thissum 0; // 累加 i~j for (int k i; k j; k) { thissum ar[k]; } // 更新最大值 if (thissum sum) { sum thissum; start i; end j; } } } return sum; }复杂度三层循环O(n³)缺点效率极低数据稍大就会超时。三、解法 2优化暴力O (n²)思路去掉最内层循环在 j 向后移动时直接累加避免重复计算。//优化 MaxSum1O(n²) int MaxSum2(const int* ar, int n) { assert(ar ! nullptr); if (n 1) return 0; int sum 0; int start -1; int end -1; for (int i 0; i n; i) { int thissum 0; // j 向后移动时直接累加 for (int j i; j n; j) { thissum ar[j]; if (thissum sum) { sum thissum; start i; end j; } } } return sum; }复杂度两层循环O(n²)优点比暴力法快很多实现简单。四、解法 3分治法O (nlogn)—— 重点推荐思路经典分治思想把数组从中间分成左右两部分递归求左半边最大子段和递归求右半边最大子段和计算跨中点的最大子段和最关键取三者最大值即为答案// 分治递归函数 int MaxSubSum(const int* ar, int left, int right) { int sum 0; // 递归出口只有一个数 if (left right) { sum ar[left] 0 ? ar[left] : 0; } else { // 1. 找中点 int mid (right - left) / 2 left; // 2. 递归左右 int leftsum MaxSubSum(ar, left, mid); int rightsum MaxSubSum(ar, mid 1, right); // 3. 求跨中点最大和左半部分从mid向左 int s1 0, lefts 0; for (int i mid; i left; --i) { lefts ar[i]; if (lefts s1) s1 lefts; } // 右半部分从mid1向右 int s2 0, rights 0; for (int i mid 1; i right; i) { rights ar[i]; if (rights s2) s2 rights; } // 4. 三者取最大 sum s1 s2; if (sum leftsum) sum leftsum; if (sum rightsum) sum rightsum; } return sum; } // 分治法入口 int MaxSum3(const int* ar, int n) { assert(ar ! nullptr); if (n 1) return 0; return MaxSubSum(ar, 0, n - 1); }复杂度每次二分 线性遍历O(nlogn)优点效率高体现高级算法思想。五、测试运行#define ArSize(ar) (sizeof(ar)/sizeof(ar[0])) int main() { int ar[] { -2,11,-4,13,-5,-2 }; int n ArSize(ar); int maxval MaxSum3(ar, n); cout maxval endl; // 输出 20 return 0; }第二部分线段树Segment Tree原理与实现一、什么是线段树线段树是一种二叉树结构每个节点代表一个区间。核心用途快速查询区间和 / 区间最值 / 区间 gcd快速进行区间更新时间复杂度构建 O (n)查询 O (logn)二、线段树核心结构用数组模拟二叉树左孩子2*node1右孩子2*node2空间大小4*n足够安全三、完整代码实现区间和查询1. 构建线段树build递归将区间拆分到叶子节点自底向上求和。2. 区间查询query判断当前区间是否在查询范围内递归合并结果。#includevector #includeiostream using namespace std; class SegmentTree { private: std::vectorint tree; // 线段树数组 int n; // 原始数据长度 // 递归构建 void build(const vectorint ar, int node, int start, int end) { if (start end) { tree[node] ar[start]; return; } int mid (end - start) / 2 start; int leftChild node * 2 1; int rightChild node * 2 2; build(ar, leftChild, start, mid); build(ar, rightChild, mid 1, end); // 父节点 左孩子 右孩子 tree[node] tree[leftChild] tree[rightChild]; } // 区间查询 [left, right] int query(int node, int start, int end, int left, int right) { // 无交集返回0 if (right start || left end) { return 0; } // 完全包含直接返回节点值 if (left start end right) { return tree[node]; } // 部分交集递归查询左右 int mid start (end - start) / 2; int leftChild 2 * node 1; int rightChild 2 * node 2; int leftsum query(leftChild, start, mid, left, right); int rightsum query(rightChild, mid 1, end, left, right); return leftsum rightsum; } public: // 构造函数创建线段树 SegmentTree(const std::vectorint ar) { n ar.size(); if (n 1) return; tree.resize(4 * n, 0); // 开4倍空间 build(ar, 0, 0, n - 1); } // 对外接口区间和查询 int rangeQuery(int left, int right) { if (left 0 || right n || left right) { return -1; } return query(0, 0, n - 1, left, right); } };四、测试运行int main() { std::vectorint ar { 1,3,5,7,9,11 }; SegmentTree segtree(ar); cout segtree.rangeQuery(0, 5) endl; // 1357911 36 cout segtree.rangeQuery(0, 2) endl; // 135 9 cout segtree.rangeQuery(1, 4) endl; // 3579 24 return 0; }输出结果高频考点总结最大子段和暴力法O (n³)简单但低效优化暴力O (n²)去掉重复累加分治法O (nlogn)面试标准解法最优解法动态规划Kadane 算法O (n)线段树用于区间查询、区间更新空间开4*n构建递归自底向上求和查询判断区间交集递归合并复杂度查询 O (logn)