一.什么是Kadane算法：
Kadane算法，又名卡丹算法，是一种高效解决最大子数组和问题的动态规划算法，该算法以简单高效而出名
二.算法核心思想：
通过迭代数组的每个元素，维护两个变量来跟踪局部最优解和全局最优解
当遍历到数组某个元素时，最大的子数组和只有两种情况，一种是以当前元素结尾，一种是以当前元素开头的新数组。
简单来说，我们需要判断的是，当前元素是加入前面的数组得到的子数组和更大，还是以当前元素开头的新子数组和更大
三.算法实现：
我们使用两个变量，一个是当前子数组和，一个是全局最大的子数组和。每遍历到一个元素时，我们都判断（当前元素+当前子数组和）与（当前元素）谁更大。再用更大的值和全局最大子数组和比较。
只需要遍历数组一次就可以找到最大的子数组和
递推公式：
maxcurNum = (maxcurNum+arr[i],arr[i]);
maxNum = (maxNum,maxcurNum);
图解：
代码实现：
int maxSubArray(int* nums) { int maxcurNum = nums[0]; int maxNum= nums[0]; for (int i = 1; i < nums.size(); i++) { maxcurNum = max(maxcurNum + nums[i], nums[i]); maxNum= max(maxNum, maxcurNum); } return maxNum; }效率分析：
- 时间复杂度：O(n)，其中 n 为 nums 数组的长度。我们只需要遍历一遍数组即可求得答案。
- 空间复杂度：O(1)。我们只需要常数空间存放若干变量。
四.真题练习：
洛谷1115：最大子字段和
题目链接P1115 最大子段和 - 洛谷
题目描述：
给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。
输入格式：
第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。
输出格式：
输出一行一个整数表示答案。
输入输出样例
输入 ：
7 2 -4 3 -1 2 -4 3
输出 ：
4
思路分析：
和例题一样，套用模板即可，注意题目数据大小，需要用long long类型存储
#include<iostream> #include<vector> #include<limits.h> using namespace std; int main() { int n; cin >> n; vector<int>vec(n); for (int i = 0;i < n;i++) { cin >> vec[i]; } long long sum = vec[0];//记录当前子数组和 long long maxx = vec[0];//记录全局最大子数组 for (int i = 1;i < n;i++) { sum = max(sum + (long long)vec[i], (long long)vec[i]); maxx = max(sum, maxx); } cout << maxx; return 0; }信息学奥赛一本通1224：最大子矩阵
题目链接：信息学奥赛一本通（C++版）在线评测系统
题目描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1×1)子矩阵。
【输入】
输入是一个N×N的矩阵。输入的第一行给出N(0<N<=100)。再后面的若干行中，依次(首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
【输出】
输出最大子矩阵的大小。
【输入样例】
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2【输出样例】
15思路分析：
由于这题是一个二维数组，我们需要将二维数组先压缩成一维数组，再通过Kadane算法找最大子数组和
我们可以创建一个一维数组，将二维数组第i列的数加到一维数组的i个元素中，这样就可以达到压缩的效果
压缩后得到的一维数组，就继续使用Kadane算法，即可得到最大子数组和，当全部情况遍历结束后，全局最大的子数组和就是最大子矩阵和
#include<iostream> #include<vector> #include<limits.h> using namespace std; int main() { //输入数据 int n; cin >> n; vector<vector<int>>vec(n,vector<int>(n)); for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { cin >> vec[i][j]; } } //处理数据 int sum = INT_MIN; for (int i = 0;i < n;i++) { //记录每列元素和 vector<int>ans(n); //从第i行开始 for (int j = i;j < n;j++) { //累加每行的元素,并在每次加完一行就进行一次计算 for (int k = 0;k < n;k++) { ans[k] += vec[j][k]; } //Kadane算法 int cur = 0; for (int z = 0;z < n;z++) { cur = max(ans[z] + cur, ans[z]); sum = max(sum, cur); } } } //输出全局最大的子数组和 cout << sum; return 0; }
