arrays - 如何找到[L，R]之间大小的最大和子数组

Question

给定一个包含正整数和负整数的数组，如何找到长度介于两者之间的最大和子数组（连续子数组L）R？

例如：如果数组是

-1 3 -2 5 3 -5 2 2

和L = 1，R = 2答案是8。

我的方法：

我不太确定如何处理这个问题。我想也许它是滑动窗口+ Kadane 的组合。我听说前缀和+滑动窗口可能是一个可能的解决方案，但我不确定如何实现它。

标签： arraysalgorithmsub-array

Answer 1

如果我正确理解您的问题，有一个 n*logn 解决方案，它确实使用前缀和和滑动窗口。这里解释一下：https ://www.geeksforgeeks.org/maximum-sum-subarray-of-size-range-lr/