大小至少为 K 的最大和子数组

给定一个数组和一个整数 k，我们的任务是找到一个包含至少 k 个元素的子数组，使其具有最大的元素之和。

示例：

> 输入：arr[] = {-4, -2, 1, -3}, k = 2

> 输出：-1

> 解释：子数组是 {-2, 1}。

>

> 输入：arr[] = {1, 1, 1, 1, 1, 1}, k = 2

> 输出：6

> 解释：子数组是 {1, 1, 1, 1, 1, 1}

点击此处尝试在线练习!

[朴素方法] – O(n^2) 时间复杂度和 O(1) 空间复杂度

这个思路很简单，我们将每个点都视为起点，并考虑所有大小为 k 或更大的子数组。我们持续跟踪最大的和，并在最后返回它。

C++

#include 
#include 
#include 
using namespace std;

int maxSum(vector &arr, int k) {
    int n = arr.size(), res = INT_MIN;

    // 遍历所有可能的起始点
    for (int i = 0; i < n; i++) {
        
        int sum = 0;
        
        for (int j = i; j = k) res = max(res, sum);
        }
    }
    return res;
}

int main() {
    vector arr = {-4, -2, 1, -3};
    int k = 2;
    cout << maxSum(arr, k) << endl;
    return 0;
}

CODEBLOCK_b127d8d4


Python

def max_sum(arr, k):
    n = len(arr)
    res = float(‘-inf‘)

    # 遍历所有可能的起始点
    for i in range(n):
        sum_ = 0
        
        for j in range(i, n):
            sum_ += arr[j]
            
            # 如果当前子数组的大小为 k
            # 或更大
            if j - i + 1 >= k:
                res = max(res, sum_)
    return res

arr = [-4, -2, 1, -3]
k = 2
print(max_sum(arr, k))

CODEBLOCK_0ccc0633


JavaScript

function maxSum(arr, k) {
    let n = arr.length, res = Number.NEGATIVE_INFINITY;

    // 遍历所有可能的起始点
    for (let i = 0; i < n; i++) {
        let sum = 0;
        
        for (let j = i; j = k) res = Math.max(res, sum);
        }
    }
    return res;
}

let arr = [-4, -2, 1, -3];
let k = 2;
console.log(maxSum(arr, k));

`

输出

-1

[更优的方法] Kadane 算法 + 滑动窗口 – O(n) 时间复杂度和 O(n) 空间复杂度

> 我们的思路是将 Kadane 算法 与滑动窗口方法结合起来，以找到一个包含至少 k 个元素且和最大的子数组。我们首先使用 Kadane 算法计算到达每个索引时所能获得的最大和，然后使用大小为 k 的滑动窗口来计算连续 k 个元素的和，对于每个窗口，我们还考虑加上该窗口之前所能获得的最大和，从而可能得到更大的子数组总和。

逐步方法：

• 使用 Kadane 算法初始化 maxSum[] 数组，用于存储到达每个索引时所能获得的最大和。
• 计算前 k 个元素的初始和作为起始窗口。
• 每次滑动一个窗口，通过添加新元素并移除第一个元素来更新窗口和。
• 对于每个窗口位置，考虑两种可能性：要么 t