算法题/滑动窗口：大小为k的子数组的最大和

题目

在给定数组中，求"连续k个元素的子数组"的最大和。

示例1：

输入：[2, 1, 5, 1, 3, 2], k=3
输出：9
解释：子数组[5, 1, 3]的和最大

示例2：

输入：[2, 3, 4, 1, 5], k=2
输出：7
解释：子数组[3, 4]的和最大

解答1：滑动窗口

Java

class MaxSumSubArrayOfSizeK {
  public static int findMaxSumSubArray(int k, int[] arr) {
    int maxSum = 0, windowSum;
    for (int i = 0; i <= arr.length - k; i++) {
      windowSum = 0;
      for (int j = i; j < i + k; j++) {
        windowSum += arr[j];
      }
      maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
  }
  
  public static void main(String[] args) {
    System.out.println("Maximum sum of a subarray of size K: "
        + MaxSumSubArrayOfSizeK.findMaxSumSubArray(3, new int[] { 2, 1, 5, 1, 3, 2 }));
    System.out.println("Maximum sum of a subarray of size K: "
        + MaxSumSubArrayOfSizeK.findMaxSumSubArray(2, new int[] { 2, 3, 4, 1, 5 }));
  }
}

JavaScript

class MaxSumSubArrayOfSizeK {
  static findMaxSumSubArray(k, arr) {
    let maxSum = 0;
    for (let i = 0; i <= arr.length - k; i++) {
      let windowSum = 0;
      for (let j = i; j < i + k; j++) {
        windowSum += arr[j];
      }
      maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
  }
}

console.log("Maximum sum of a subarray of size K: " + MaxSumSubArrayOfSizeK.findMaxSumSubArray(3, [2, 1, 5, 1, 3, 2]));
console.log("Maximum sum of a subarray of size K: " + MaxSumSubArrayOfSizeK.findMaxSumSubArray(2, [2, 3, 4, 1, 5]));

Python

class MaxSumSubArrayOfSizeK:
    @staticmethod
    def findMaxSumSubArray(k, arr):
        maxSum = 0
        for i in range(len(arr) - k + 1):
            windowSum = 0
            for j in range(i, i + k):
                windowSum += arr[j]
            maxSum = max(maxSum, windowSum)

        return maxSum


print("Maximum sum of a subarray of size K:",
      MaxSumSubArrayOfSizeK.findMaxSumSubArray(3, [2, 1, 5, 1, 3, 2]))
print("Maximum sum of a subarray of size K:",
      MaxSumSubArrayOfSizeK.findMaxSumSubArray(2, [2, 3, 4, 1, 5]))

Go

package main

import (
	"fmt"
)

func findMaxSumSubArray(k int, arr []int) int {
	maxSum := 0
	for i := 0; i <= len(arr)-k; i++ {
		windowSum := 0
		for j := i; j < i+k; j++ {
			windowSum += arr[j]
		}
		if windowSum > maxSum {
			maxSum = windowSum
		}
	}
	return maxSum
}

func main() {
	fmt.Println("Maximum sum of a subarray of size K:", findMaxSumSubArray(3, []int{2, 1, 5, 1, 3, 2}))
	fmt.Println("Maximum sum of a subarray of size K:", findMaxSumSubArray(2, []int{2, 3, 4, 1, 5}))