算法学习

简介

记录本人算法学习

kadane算法（处理最长连续子数列和）

本质是动态规划结合贪心算法，时间复杂度为o(n)。

递推表达式为:

current_max = std::max(arr[i], current_max + arr[i]);

max_so_far = std::max(max_so_far, current_max);

其中arr[i]是存储数据元素的数组，current_max是局部最大值，max_so_far是全局最大值。

通过这一算法可以极大地减小时间复杂度。