核心内容摘要
开启私密视觉盛宴，点亮你的非凡世界
什么是Kadane算法Kadane算法又名卡丹算法是一种高效解决最大子数组和问题的动态规划算法该算法以简单高效而出名
算法核心思想通过迭代数组的每个元素维护两个变量来跟踪局部最优解和全局最优解当遍历到数组某个元素时最大的子数组和只有两种情况一种是以当前元素结尾一种是以当前元素开头的新数组。
简单来说我们需要判断的是当前元素是加入前面的数组得到的子数组和更大还是以当前元素开头的新子数组和更大
算法实现我们使用两个变量一个是当前子数组和一个是全局最大的子数组和。
每遍历到一个元素时我们都判断当前元素当前子数组和与当前元素谁更大。
再用更大的值和全局最大子数组和比较。
只需要遍历数组一次就可以找到最大的子数组和递推公式maxcurNum (maxcurNumarr[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(
。
我们只需要常数空间存放若干变量。
真题练习洛谷1115最大子字段和题目链接P1115 最大子段和 - 洛谷题目描述给出一个长度为 n 的序列 a选出其中连续且非空的一段使得这段和最大。
输入格式第一行是一个整数表示序列的长度 n。
第二行有 n 个整数第 i 个整数表示序列的第 i 个数字 ai。
输出格式输出一行一个整数表示答案。
输入输出样例输入 7 2 -4 3 -1 2 -4 3输出 4思路分析和例题一样套用模板即可注意题目数据大小需要用long long类型存储#includeiostream #includevector #includelimits.h using namespace std; int main() { int n; cin n; vectorintvec(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×
子矩阵。
【输入】输入是一个N×N的矩阵。
输入的第一行给出N(0N
。
再后面的若干行中依次(首先从左到右给出第一行的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算法即可得到最大子数组和当全部情况遍历结束后全局最大的子数组和就是最大子矩阵和#includeiostream #includevector #includelimits.h using namespace std; int main() { //输入数据 int n; cin n; vectorvectorintvec(n,vectorint(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) { //记录每列元素和 vectorintans(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; }