高级算法
讲师：neetcode.io
口袋资源独家Neetcode付费课程，独家中英文字幕，配套资料齐全！
用不到1/10的价格，即可享受同样的高品质课程，且可以完全拥有，随时随地都可以任意观看和分享。
Kadane算法
Kadane 算法是一种贪婪/动态编程算法，可用于数组问题，将时间复杂度降至�(�)(n O(�)。它用于计算在特定位置结束的子数组的最大和。
动机
假设我们得到了以下问题：
问：找出总和最大的非空子数组。
这道题目要求我们在数组中找出一组相邻值的最大和。然后要求我们返回该总和。
如果我们暂时不考虑卡达内算法，蛮干的方法就是遍历每一个子数组并计算总和，同时跟踪最大总和。这样做是可行的，但会有大量重复工作。外 for 循环每迭代一次，内循环就做一次线性工作。这使得复杂度为�(n2) O(n 2)。
def bruteForce(nums):
maxSum = nums[0]
for i in range(len(nums)):
curSum = 0
for j in range(i, len(nums)):
curSum += nums[j]
maxSum = max(maxSum, curSum)
return maxSum复制
我们可以做得更好。
卡丹算法告诉我们，有一种方法只需对数组进行一次传递，就能计算出最大和，从而将复杂度降至线性时间。让我们看看如何做到这一点。
由于我们正在寻找最大的和，所以最好避免负数，因为我们知道这与问题的要求相矛盾。负数只会使我们的和变小。卡丹算法在数组上运行一个 for 循环，在每次迭代开始时，如果当前总和为负数，就会将当前总和重置为零。这样，我们就能确保一次通过，并在线性时间内解决问题。这就是代码和可视化的效果。请记住，这里的关键是，如果我们遇到的子数组的和为负数，我们就丢弃它，只要它的和为正数，我们就继续考虑它。
def kadanes(nums):
maxSum = nums[0]
curSum = 0
for n in nums:
curSum = max(curSum, 0)
curSum += n
maxSum = max(maxSum, curSum)
return maxSum
推拉窗
有时，问题可能要求返回包含最大和的实际子数组，而不仅仅是和本身？在以前的实现中，我们不一定需要两个显式指针来跟踪子数组，但实际上我们可以通过跟踪一个 “窗口 “来做到这一点。在这种情况下，”窗口 “指的是一个连续的子数组，它不会打破我们对总和保持正值的限制。
为此，我们可以有一个左指针L = 0 和一个右指针R。由于我们需要的是总和最大的子数组，因此我们还可以有另外两个指针，即maxL和maxR，这两个指针可以跟踪到目前为止包含最大总和的子数组。这样，当我们移动L和R 时，就不会丢失它们。与之前类似，如果当前总和为负，我们可以将左指针一直移动到右指针。这意味着我们的约束被打破，我们将删除左侧的所有元素并启动一个新窗口。
def slidingWindow(nums):
maxSum = nums[0]
curSum = 0
maxL, maxR = 0, 0
L = 0
for R in range(len(nums)):
if curSum < 0:
curSum = 0
L = R
curSum += nums[R]
if curSum > maxSum:
maxSum = curSum
maxL, maxR = L, R
return [maxL, maxR]
子数组指数组中连续的部分。
时间复杂性
由于我们只进行一次传递，因此时间复杂度降为�(�)nO(�)。下一章将详细讨论这个问题。
结束语
接下来，让我们正式了解一下滑动窗口技术。滑动窗口技术有两种变体，即固定滑动窗口和可变大小滑动窗口，这两种技术都适用于不同类型的问题。
