Kadane算法详解

一.什么是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)子矩阵。

【输入】

【输出】

【输入样例】

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; }