当前位置：首页 > news >正文

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

news 2026/8/6 14:33:59

前言

最大子段和是最经典的入门题之一；而线段树则是处理区间查询、区间更新的高级数据结构，是进阶必备。

本文将基于我提供的完整代码，分两大部分精讲：

最大子段和问题：暴力 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 向后移动时直接累加，避免重复计算。

//优化 MaxSum1（O(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; } // 右半部分（从mid+1向右） 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*node+1
右孩子：2*node+2
空间大小：4*n（足够安全）

三、完整代码实现（区间和查询）

1. 构建线段树（build）

递归将区间拆分到叶子节点，自底向上求和。

2. 区间查询（query）

判断当前区间是否在查询范围内，递归合并结果。

#include<vector> #include<iostream> using namespace std; class SegmentTree { private: std::vector<int> tree; // 线段树数组 int n; // 原始数据长度 // 递归构建 void build(const vector<int>& 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::vector<int>& 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::vector<int> ar = { 1,3,5,7,9,11 }; SegmentTree segtree(ar); cout << segtree.rangeQuery(0, 5) << endl; // 1+3+5+7+9+11 = 36 cout << segtree.rangeQuery(0, 2) << endl; // 1+3+5 = 9 cout << segtree.rangeQuery(1, 4) << endl; // 3+5+7+9 = 24 return 0; }

输出结果：